检索结果-内蒙古大学图书馆

Fully dynamic Algorithm for Recognition and Modular Decomposition of Permutation Graphs

ALGORITHMICA 2010年第2期58卷 405-432页

作者： Crespelle, Christophe Paul, Christophe Univ Montpellier 2 LIRMM Montpellier France LIRMM CNRS Montpellier France

This paper considers the problem of maintaining a compact representation (O(n) space) of permutation graphs under vertex and edge modifications (insertion or deletion). That representation allows us to answer adjacency queries in O(1) time. The approach is based on a fully dynamic modular decomposition algorithm for permutation graphs that works in O(n) time per edge and vertex modification. We thereby obtain a fully dynamic algorithm for the recognition of permutation graphs.

关键词： dynamic algorithms Permutation graphs Modular decomposition

来源：评论

学校读者我要写书评

暂无评论

Union and split operations on dynamic trapezoidal maps

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2000年第3-4期17卷 153-163页

作者： Teillaud, M INRIA F-06902 Sophia Antipolis France

We propose algorithms to perform two new operations on an arrangement of line segments in the plane, represented by a trapezoidal map: the split of the map along a given vertical line D, and the union of two trapezoidal maps computed in two vertical slabs of the plane that are adjacent through a vertical line D. The data structure we use is a modified Influence Graph, still allowing dynamic insertions and deletions of line segments in the map. The algorithms for both operations run in O(s(D) log n + log(2) n) time, where n is the number of line segments in the map, and so is the number of line segments intersected by D. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： dynamic algorithms randomized algorithms data structures parallel data structures trapezoidal map

来源：评论

学校读者我要写书评

暂无评论

FULLY dynamic BICONNECTIVITY IN GRAPHS

引用

ALGORITHMICA 1995年第6期13卷 503-538页

作者： HENZINGER, MR Department of Computer Science Cornell University Ithaca USA

We present an algorithm for maintaining the biconnected components of a graph during a sequence of edge insertions and deletions. It requires linear storage and preprocessing time. The amortized running time for insertions and for deletions is O(m(2/3)), where m is the number of edges in the graph. Any query of the form 'Are the vertices u and v biconnected?' can be answered in time O(1). This is the first sublinear algorithm for this problem. We can also output all articulation points separating any two vertices efficiently. If the input is a plane graph, the amortized running time for insertions and deletions drops to O(root n log n) and the query time is O(log(2) n), where n is the number of vertices in the graph. The best previously known solution takes time O(n(2/3)) per update or query.

关键词： GRAPH algorithms dynamic algorithms DATA STRUCTURES GRAPH CONNECTIVITY

来源：评论

学校读者我要写书评

暂无评论

dynamic location management for mobile computing

引用

TELECOMMUNICATION SYSTEMS 2003年第1-4期22卷 169-187页

作者： Subrata, R Zomaya, AY Univ Sydney Sch Informat Technol Sydney NSW 2006 Australia Univ Western Australia Dept Elect & Elect Engn Parallel Comp Res Lab Nedlands WA 6907 Australia

This paper presents a dynamic and individualized location update scheme that considers each user's mobility patterns. The mobility patterns are used to create individualized location areas for each user. The proposed scheme is flexible and can be used in network with arbitrary cell topologies. The scheme, along with other existing schemes is simulated using realistic users' mobility and call arrival patterns, and network topology. The simulated environment consists of 90 cells representing the geographical area of the San Francisco bay, and 66,550 mobile users representing the typical classes of users that are normally present in a real cellular network. Results show the proposed scheme gives lower overall signaling costs, resulting in savings on the limited radio bandwidth that may have otherwise been used for location updates and paging.

关键词： dynamic algorithms location management mobile computing wireless networks

来源：评论

学校读者我要写书评

暂无评论

Emergent role of dynamic optimization in cardiac resynchronization therapy: Systematic review and network meta-analysis

引用

ESC HEART FAILURE 2024年第6期11卷 4046-4060页

作者： Zsigmond, Elod-Janos Masszi, Richard Ehrenberger, Reka Turan, Caner Fehervari, Peter Gede, Noemi Hegyi, Peter Molnar, Zsolt Trasy, Domonkos Duray, Gabor Zoltan Semmelweis Univ Ctr Translat Med Ullo Ut 26 H-1085 Budapest Hungary Cent Hosp Northern Pest Mil Hosp Dept Cardiol Robert Karoly Korut 44 H-1134 Budapest Hungary Univ Szeged Doctoral Sch Clin Med Szeged Hungary Semmelweis Univ Heart & Vasc Ctr Budapest Hungary Semmelweis Univ Dept Anesthesiol & Intens Therapy Budapest Hungary Semmelweis Univ Inst Pancreat Dis Budapest Hungary Univ Pecs Inst Translat Med Med Sch Pecs Hungary Poznan Univ Med Sci Dept Anesthesiol & Intens Therapy Poznan Poland

AimsSuboptimal device programming is frequent in non-responders to cardiac resynchronization therapy (CRT). However, the role of device optimization and the most appropriate technique are still unknown. The aim of our study was to analyse the effect of different CRT optimization techniques within a network *** systematic search was conducted on MEDLINE, Embase and CENTRAL for studies comparing outcomes with empirical device settings or optimization using echocardiography, static algorithms or dynamic algorithms. Studies investigating the effect of optimization in non-responders were also *** total of 17 studies with 4346 patients were included in the quantitative analysis. Of the treatments and outcomes examined, a significant difference was found only between dynamic algorithms and echocardiography, with the former leading to a higher echocardiographic response rate [odds ratio (OR): 2.02, 95% confidence interval (CI) 1.21-3.35], lower heart failure hospitalization rate (OR: 0.75, 95% CI 0.57-0.99) and greater improvement in 6-minute walk test [mean difference (MD): 45.52 m, 95% credible interval (CrI) 3.91-82.44 m]. We found no significant difference between empirical settings, static algorithms and dynamic algorithms. Seven studies with 228 patients reported response rates after optimization in non-responders. Altogether, 34.3%-66.7% of initial non-responders showed improvement after optimization, depending on response *** the time of CRT implantation, dynamic algorithms may serve as a resource-friendly alternative to echocardiographic optimization, with similar or better mid-term outcomes. However, their superiority over empirical device settings needs to be investigated in further trials. For non-responders, CRT optimization should be considered, as the majority of patients experience improvement. In our study, we analyzed data from 17 studies on different cardiac resynchronization therapy optimization techniq

关键词： cardiac resynchronization therapy device optimization dynamic algorithms echocardiography empirical settings

来源：评论

学校读者我要写书评

暂无评论

dynamic multi-dimensional bin packing

引用

JOURNAL OF DISCRETE algorithms 2010年第4期8卷 356-372页

作者： Epstein, Leah Levy, Meital Univ Haifa Dept Math IL-31905 Haifa Israel Tel Aviv Univ Sch Comp Sci Tel Aviv Israel

A natural generalization of the classical online bin packing problem is the dynamic bin packing problem introduced by Coffman et al. (1983) [7]. In this formulation, items arrive and depart and the objective is to minimize the maximal number of bins ever used over all times. We study the oriented multi-dimensional dynamic bin packing problem for two dimensions, three dimensions and multiple dimensions. Specifically, we consider dynamic packing of squares and rectangles into unit squares and dynamic packing of three-dimensional cubes and boxes into unit cubes. We also study dynamic d-dimensional hypercube and hyperbox packing. For dynamic d-dimensional box packing we define and analyze the algorithm NFDH for the offline problem and present a dynamic version. This algorithm was studied before for rectangle packing and for square packing and was generalized only for multi-dimensional cubes. We present upper and lower bounds for each of these cases. (C) 2010 Elsevier B. V. All rights reserved.

关键词： Bin packing Online algorithms dynamic algorithms Multi-dimensional packing

来源：评论

学校读者我要写书评

暂无评论

On-the-Fly Static Analysis via dynamic Bidirected Dyck Reachability

引用

PROCEEDINGS OF THE ACM ON PROGRAMMING LANGUAGES-PACMPL 2024年第POPL期8卷 1239-1268页

作者： Krishna, Shankaranarayanan Lal, Aniket Pavlogiannis, Andreas Tuppe, Omkar Indian Inst Technol Mumbai Maharashtra India Aarhus Univ Aabogade 34 DK-8200 Aarhus Denmark

Dyck reachability is a principled, graph-based formulation of a plethora of static analyses. Bidirected graphs are used for capturing dataflow through mutable heap data, and are usual formalisms of demand-driven points-to and alias analyses. The best (offline) algorithm runs in O(m + n . alpha(n)) time, where n is the number of nodes and m is the number of edges in the flow graph, which becomes O(n(2)) in the worst case. In the everyday practice of program analysis, the analyzed code is subject to continuous change, with source code being added and removed. On-the-fly static analysis under such continuous updates gives rise to dynamic Dyck reachability, where reachability queries run on a dynamically changing graph, following program updates. Naturally, executing the offline algorithm in this online setting is inadequate, as the time required to process a single update is prohibitively large. In this work we develop a novel dynamic algorithm for bidirected Dyck reachability that has O(n . alpha(n)) worst-case performance per update, thus beating the O(n(2)) bound, and is also optimal in certain settings. We also implement our algorithm and evaluate its performance on on-the-fly data-dependence and alias analyses, and compare it with two best known alternatives, namely (i) the optimal offline algorithm, and (ii) a fully dynamic Datalog solver. Our experiments show that our dynamic algorithm is consistently, and by far, the top performing algorithm, exhibiting speedups in the order of 1000X. The running time of each update is almost always unnoticeable to the human eye, making it ideal for the on-the-fly analysis setting.

关键词： CFL reachability static analysis dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

Fully dynamic Matching and Ordered Ruzsa-Szemeredi Graphs 65

Fully Dynamic Matching and Ordered Ruzsa-Szemeredi Graphs

引用

65th Symposium on Foundations of Computer Science

作者： Behnezhad, Soheil Ghafari, Alma Northeastern Univ Khoury Coll Comp Sci Boston MA 02115 USA

ISBN: (纸本)9798331516758;9798331516741

We study the fully dynamic maximum matching problem. In this problem, the goal is to efficiently maintain an approximate maximum matching of a graph that is subject to edge insertions and deletions. Our focus is particularly on algorithms that maintain the edges of a (1 - epsilon)-approximate maximum matching for an arbitrarily small constant epsilon > 0. Until recently, the fastest known algorithm for this problem required Theta(n) time per update where n is the number of vertices. This bound was slightly improved to n/(log * n)(Omega(1)) by Assadi, Behnezhad, Khanna, and Li [STOC'23] and very recently to n/2(Omega(root log n)) by Liu [FOCS'24]. Whether this can be improved to n(1-Omega(1)) remains a major open problem. In this paper, we introduce Ordered Ruzsa-Szemeredi (ORS) graphs (a generalization of Ruzsa-Szemeredi graphs) and show that the complexity of dynamic matching is closely tied to them. For delta > 0, define ORS(delta n) to be the maximum number of matchings M-1, ... , M-t, each of size delta n, that one can pack in an n-vertex graph such that each matching M-i is an induced matching in subgraph M-1 boolean OR ... boolean OR M-i. We show that there is a randomized algorithm that maintains a (1 - epsilon)-approximate maximum matching of a fully dynamic graph in (O) over tilde(root n(1+epsilon) . ORS(Theta(epsilon)(n))) amortized update-time. While the value of ORS(Theta(n)) remains unknown and is only upper bounded by n(1-o(1)), the densest construction known from more than two decades ago only achieves ORS(Theta(n)) >= n(1/Theta(log log n)) = n(o(1)) [Fischer et al. STOC'02]. If this is close to the right bound, then our algorithm achieves an update-time of root n(1+O(epsilon)), resolving the aforementioned longstanding open problem in dynamic algorithms in a strong sense.

关键词： Approximate Matching dynamic algorithms Rusza-Szemeredi Graphs

来源：评论

学校读者我要写书评

暂无评论

Fully dynamic delaunay triangulation in logarithmic expected time per operation

引用

Computational Geometry: Theory and Applications 1992年第2期2卷 55-80页

作者： Devillers, Olivier Meiser, Stefan Teillaud, Monique INRIA 06902 Sophia-Antipolis cedex B.P. 93 France Max Planck Institut für Informatik W-6600 Saarbrücken Germany INRIA 06902 Sophia-Antipolis cedex B.P. 93 France

The Delaunay Tree is a hierarchical data structure that has been introduced in [6] and analyzed in [7, 4]. For a given set of sites L in the plane and an order of insertion for these sites, the Delaunay Tree stores all the successive Delaunay triangulations. As proved before, the Delaunay Tree allows the insertion of a site in logarithmic expected time and linear expected space, when the insertion sequence is randomized. In this paper, we describe an algorithm maintaining the Delaunay Tree under insertions and deletions of sites. This can be done in O(log n) expected time for an insertion and O(log log n) expected time for a deletion, where n is the number of sites currently present in the structure. For deletions, by expected time, we mean averaging over all already inserted sites for the choice of the deleted sites. These results are optimal. The algorithm has been effectively coded and experimental results are given. © 1992.

关键词： Delaunay triangulation dynamic algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

What you see is what you code: A radically dynamic algorithm visualization development model for novice learners

What you see is what you code: A radically dynamic algorithm...

引用

IEEE Symposium on Visual Languages and Human-Centric Computing

作者： Hundhausen, CD Brown, JL Washington State Univ Sch Elect Engn & Comp Sci Visualizat & End User Programming Lab Pullman WA 99164 USA

ISBN: (纸本)0769524435

Pedagogical algorithm visualization systems produce graphical representations that aim to assist learners in understanding the dynamic behavior of computer algorithms. In order to foster active learning, educators have explored algorithm visualization systems that empower learners to construct their own visualizations of algorithms tinder study. Notably, these systems support a similar development model in which coding the algorithm is temporally distinct from viewing and interacting with the resulting visualization. To explore the benefits of narrowing the gap between coding an algorithm and viewing its visualization, we have implemented "What You See Is What You Code, " a novel, "radically dynamic" development model to facilitate learner-constructed algorithm visualizations. In this model, the line of algorithm code currently being edited is reevaluated on every edit, leading to the dynamic update of an accompanying visualizalion of the algorithm. Analysis of usability studies involving introductory computer science students suggests that the immediacy of the model's feedback can help novices to quickly identify and correct programming errors, and ultimately to understand their code's execution.

关键词： computer aided instruction computer science education program debugging program visualisation teaching active learning algorithm behavior understanding algorithm code code execution computer science students graphical representation learner assistance mo Debugging development model computer science education Visualization Graphic methods algorithms viewing visualization system dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：