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

An Invitation to dynamic graph Problems: Lower Bounds - III

RESONANCE-JOURNAL OF SCIENCE EDUCATION 2022年第10期27卷 1777-1787页

作者： Kashyop, Manas Jyoti Narayanaswamy, N. S. Inst Math Sci Chennai Tamil Nadu India IIT Madras Dept CSE Chennai Tamil Nadu India

In this section of Resonance, we invite readers to pose questions likely to be raised in a classroom situation. We may suggest strategies for dealing with them, or invite responses, or both. "Classroom" is equally a forum for raising broader issues and sharing personal experiences and viewpoints on matters related to teaching and learning science. We present a three-part paper consisting of a survey of some of the extensively used techniques in the dynamic graph model that have appeared recently in the computer science community. In this third part of the three-part survey paper, we present a set of techniques to prove lower bounds for dynamic graph problems. In the first part(1) of the survey, we presented the motivation for research in dynamic graph algorithms and an introduction to dynamic graphs. In the second part(2) of the survey, we presented a set of techniques to prove upper bounds for dynamic graph problems. A dynamic graph is a graph that has a fixed vertex set and an evolving edge set. The edge set keeps changing due to the insertion of a new edge or the deletion of an existing edge. Research in dynamic graphs has succeeded in obtaining efficient upper bounds for an extensive collection of problems. However, there are problems of stubborn nature. Such complex problems lead to the investigation of lower bounds.

关键词： dynamic graph algorithms adversary cell-probe lower bounds conditional lower bound

来源：评论

学校读者我要写书评

暂无评论

Super-Logarithmic Lower Bounds for dynamic graph Problems 64

Super-Logarithmic Lower Bounds for Dynamic Graph Problems

引用

64th Annual IEEE Symposium on the Foundations of Computer Science (FOCS)

作者： Larsen, Kasper Green Yu, Huacheng Aarhus Univ Aarhus Denmark Princeton Univ Princeton NJ USA

ISBN: (纸本)9798350318944

In this work, we prove a (Omega) over tilde (lg(3/2) n) unconditional lower bound on the maximum of the query time and update time for dynamic data structures supporting reachability queries in n-node directed acyclic graphs under edge insertions. This is the first super-logarithmic lower bound for any natural graph problem. In proving the lower bound, we also make novel contributions to the state-of-the-art data structure lower bound techniques that we hope may lead to further progress in proving lower bounds.

关键词： cell-probe model data structure lower bounds dynamic reachability dynamic graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Parallel Batch-dynamic graph Connectivity 19

Parallel Batch-Dynamic Graph Connectivity

引用

31st ACM Symposium on Parallelism in algorithms and Architecturess (SPAA)

作者： Acar, Umut A. Anderson, Daniel Blelloch, Guy E. Dhulipala, Laxman Carnegie Mellon Univ Pittsburgh PA 15213 USA

ISBN: (纸本)9781450361842

In this paper, we study batch parallel algorithms for the dynamic connectivity problem, a fundamental problem that has received considerable attention in the sequential setting. The best sequential algorithm for dynamic connectivity is the elegant level-set algorithm of Holm, de Lichtenberg and Thorup (HDT), which achieves O(1g(2) n) amortized time per edge insertion or deletion, and O(1g n) time per query. We design a parallel batch-dynamic connectivity algorithm that is work-efficient with respect to the HDT algorithm for small batch sizes, and is asymptotically faster when the average batch size is sufficiently large. Given a sequence of batched updates, where A is the average batch size of all deletions, our algorithm achieves O(1g n lg(1 + n/A)) expected amortized work per edge insertion and deletion and O (1g(3) n) depth w.h.p. Our algorithm answers a batch of k connectivity queries in O(k lg(1 + n/ k)) expected work and O(1g n) depth w.h.p. To the best of our knowledge, our algorithm is the first parallel batch-dynamic algorithm for connectivity.

关键词： parallel graph algorithms graph connectivity dynamic graph algorithms graph algorithms

来源：评论

学校读者我要写书评

暂无评论

dynamic CONNECTIVITY: CONNECTING TO NETWORKS AND GEOMETRY

引用

SIAM JOURNAL ON COMPUTING 2011年第2期40卷 333-349页

作者： Chan, Timothy M. Patrascu, Mihai Roditty, Liam Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada AT&T Labs Florham Pk NJ 07932 USA Bar Ilan Univ Dept Comp Sci IL-52900 Ramat Gan Israel

dynamic connectivity is a well-studied problem, but so far the most compelling progress has been confined to the edge-update model: maintain an understanding of connectivity in an undirected graph, subject to edge insertions and deletions. In this paper, we study two more challenging, yet equally fundamental, problems. Subgraph connectivity asks us to maintain an understanding of connectivity under vertex updates: updates can turn vertices on and off, and queries refer to the subgraph induced by on vertices. (For instance, this is closer to applications in networks of routers, where node faults may occur.) We describe a data structure supporting vertex updates in (O) over tilde (m(2/3)) amortized time, where m denotes the number of edges in the graph. This greatly improves upon the previous result [T. M. Chan, in Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), 2002, pp. 7-13], which required fast matrix multiplication and had an update time of O(m(0.94)). The new data structure is also simpler. Geometric connectivity asks us to maintain a dynamic set of n geometric objects and query connectivity in their intersection graph. (For instance, the intersection graph of balls describes connectivity in a network of sensors with bounded transmission radius.) Previously, nontrivial fully dynamic results were known only for special cases like axis-parallel line segments and rectangles. We provide similarly improved update times, (O) over tilde (n(2/3)), for these special cases. Moreover, we show how to obtain sublinear update bounds for virtually all families of geometric objects which allow sublinear time range queries. In particular, we obtain the first sublinear update time for arbitrary two-dimensional line segments: O*(n(9/10));for d-dimensional simplices: O*(n(1-1/d(2d+1)));and for d-dimensional balls: O*(n(1-1/(d+1)(2d+3))).

关键词： data structures dynamic graph algorithms connectivity computational geometry

来源：评论

学校读者我要写书评

暂无评论

A new approach to dynamic all pairs shortest paths

引用

JOURNAL OF THE ACM 2004年第6期51卷 968-992页

作者： Demetrescu, C Italiano, GF Univ Roma La Sapienza Rome Italy Univ Roma Tor Vergata Rome Italy

We study novel combinatorial properties of graphs that allow us to devise a completely new approach to dynamic all pairs shortest paths problems. Our approach yields a fully dynamic algorithm for general directed graphs with non-negative real-valued edge weights that supports any sequence of operations in O(n(2) log(3) n) amortized time per update and unit worst-case time per distance query, where n is the number of vertices. We can also report shortest paths in optimal worst-case time. These bounds improve substantially over previous results and solve a long-standing open problem. Our algorithm is deterministic, uses simple data structures, and appears to be very fast in practice.

关键词： algorithms dynamic graph algorithms shortest paths

来源：评论

学校读者我要写书评

暂无评论

dynamic APPROXIMATE ALL-PAIRS SHORTEST PATHS: BREAKING THE O(mn) BARRIER AND DERANDOMIZATION

引用

SIAM JOURNAL ON COMPUTING 2016年第3期45卷 947-1006页

作者： Henzinger, Monika Krinninger, Sebastian Nanongkai, Danupon Univ Vienna Fac Comp Sci A-1010 Vienna Austria

We study dynamic (1 + epsilon)-approximation algorithms for the all-pairs shortest paths problem in unweighted undirected n-node m-edge graphs under edge deletions. The fastest algorithm for this problem is a randomized algorithm with a total update time of (O) over tilde (mn/epsilon) and constant query time by Roditty and Zwick [SIAM J. Comput., 41 (2012), pp. 670-683]. The fastest deterministic algorithm is from a 1981 paper by Even and Shiloach [J. ACM, 28 (1981), pp. 1-4];it has a total update time of O(mn(2)) and constant query time. We improve these results as follows: (1) We present an algorithm with a total update time of (O) over tilde (n(5/2)/epsilon) and constant query time that has an additive error of 2 in addition to the 1 + epsilon multiplicative error. This beats the previous (O) over tilde (mn/epsilon) time when m = Omega(n(3/2)). Note that the additive error is unavoidable since, even in the static case, an O(n(3-delta))-time (a so-called truly subcubic) combinatorial algorithm with 1 + epsilon multiplicative error cannot have an additive error less than 2 - epsilon, unless we make a major breakthrough for Boolean matrix multiplication [D. Dor, S. Halrepin, and U. Zwick, SIAM J. Comput., 29 (2000), pp. 1740-1759] and many other long-standing problems [V. Vassilevska Williams and R. Williams, Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 2010, pp. 645-654]. The algorithm can also be turned into a (2 + epsilon)-approximation algorithm (without an additive error) with the same time guarantees, improving the recent (3 + epsilon)-approximation algorithm with (O) over tilde (n(5/2+O(root log(1/epsilon)/log n))) running time of Bernstein and Roditty [Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete algorithms, 2011, pp. 1355-1365] in terms of both approximation and time guarantees. (2) We present a deterministic algorithm with a total update time of (O) over tilde (mn/epsilon) and a query time

关键词： dynamic graph algorithms all-pairs shortest paths derandomization emulator

来源：评论

学校读者我要写书评

暂无评论

dynamic bottleneck optimization for k-edge and 2-vertex connectivity

引用

INFORMATION PROCESSING LETTERS 2008年第6期106卷 251-257页

作者： Telelis, Orestis A. Zissimopoulos, Vassilis Univ Aarhus Dept Comp Sci DK-8000 Aarhus C Denmark Univ Athens Dept Informat & Telecommun GR-10679 Athens Greece

We consider the problem of updating efficiently the minimum value b over a weighted graph, so that edges with a cost less than b induce a spanning subgraph satisfying a k-edge or 2-vertex connectivity constraint, when the cost of an edge of the graph is updated. Our results include update algorithms of almost linear time (up to poly-logarithmic factors) in the number of vertices for all considered connectivity constraints (for fixed k), and a worst case construction showing that these algorithms are almost optimal in their class. (C) 2007 Elsevier B.V. All rights reserved.

关键词： data structures dynamic graph algorithms graph connectivity

来源：评论

学校读者我要写书评

暂无评论

Trade-offs for fully dynamic transitive closure on DAGs:: Breaking through the O(n²) barrier

引用

JOURNAL OF THE ACM 2005年第2期52卷 147-156页

作者： Demetrescu, C Italiano, GF Univ Roma La Sapienza Rome Italy Univ Roma Tor Vergata Rome Italy

We present an algorithm for directed acyclic graphs that breaks through the O(n(2)) barrier on the single-operation complexity of fully dynamic transitive closure, where n is the number of edges in the graph. We can answer queries in O(n(epsilon)) worst-case time and perform updates in O(n(omega(1, epsilon, 1)-epsilon) + n(1+epsilon)) worst-case time, for any epsilon is an element of [0, 1], where omega(1, epsilon, 1) is the exponent of the multiplication of an n x n(epsilon) matrix by an n(epsilon) x n matrix. The current best bounds on omega(1, epsilon, 1) imply an O(n(0.575)) query time and an O(n(1.575)) update time in the worst case. Our subquadratic algorithm is randomized, and has one-sided error. As an application of this result, we show how to solve single-source reachability in O(n(1.575)) time per update and constant time per query.

关键词： algorithms dynamic graph algorithms transitive closure

来源：评论

学校读者我要写书评

暂无评论

A Faster and Simpler Fully dynamic Transitive Closure

引用

ACM TRANSACTIONS ON algorithms 2008年第1期4卷 1–16页

作者： Roditty, Liam Weizmann Inst Sci Fac Math & Comp Sci IL-76100 Rehovot Israel

We obtain a new fully dynamic algorithm for maintaining the transitive closure of a directed graph. Our algorithm maintains the transitive closure matrix in a total running time of O(mn + (ins + del) . n(2)), where ins (del) is the number of insert (delete) operations performed. Here n is the number of vertices in the graph and m is the initial number of edges in the graph. Obviously, reachability queries can be answered in constant time. The algorithm uses only O(n(2)) time which is essentially optimal for maintaining the transitive closure matrix. Our algorithm can also support path queries. If v is reachable from u, the algorithm can produce a path from u to v in time proportional to the length of the path. The best previously known algorithm for the problem is due to Demetrescu and Italiano [2000]. Their algorithm has a total running time of O(n(3) + (ins + del) . n(2)). The query time is also constant. In addition, we also present a simple algorithm for directed acyclic graphs (DAGs) with a total running time of O(mn + ins . n(2) + del). Our algorithms are obtained by combining some new ideas with techniques of Italiano [1986, 1988], King [1999], King and Thorup [2001] and Frigioni et al. [2001]. We also note that our algorithms are extremely simple and can be easily implemented.

关键词： dynamic graph algorithms reachability directed graph

来源：评论

学校读者我要写书评

暂无评论

Efficient and dynamic algorithms for Alternating Buchi Games and Maximal End-Component Decomposition

引用

JOURNAL OF THE ACM 2014年第3期61卷 1–40页

作者： Chatterjee, Krishnendu Henzinger, Monika IST Austria A-3400 Klosterneuburg Austria Univ Vienna Res Grp Theory & Applicat Algorithms A-1090 Vienna Austria

The computation of the winning set for Buchi objectives in alternating games on graphs is a central problem in computer-aided verification with a large number of applications. The long-standing best known upper bound for solving the problem is (O) over tilde (n. m), where n is the number of vertices and m is the number of edges in the graph. We are the first to break the 0(n m) boundary by presenting a new technique that reduces the running time to 0(n(2)). This bound also leads to O(n(2))-time algorithms for computing the set of almost-sure winning vertices for Buchi objectives (1) in alternating games with probabilistic transitions (improving an earlier bound of 0(n,. m)), (2) in concurrent graph games with constant actions (improving an earlier bound of O(n(3))), and (3) in Markov decision processes (improving for m > n(4/3) an earlier bound of O(m.,root m)). We then show how to maintain the winning set for Buchi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in 0(n) amortized time per operation. Our algorithms are the first dynamic algorithms for this problem. We then consider another core graph theoretic problem in verification of probabilistic systems, namely computing the maximal end-component decomposition of a graph. We present two improved static algorithms for the maximal end-component decomposition problem. Our first algorithm is an O(*** m)-time algorithm, and our second algorithm is an 0(n2)-time algorithm which is obtained using the same technique as for alternating Buchi games. Thus, we obtain an O(min{m . root m, n(2)})-time algorithm improving the long-standing O(n . m) time bound. Finally, we show how to maintain the maximal end-component decomposition of a graph under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per edge deletion, and O(m) worst-case time per edge insertion. Again, our algorithms are the first dynamic algorithms for this problem.

关键词： algorithms Verification graph games Buchi objectives graph algorithms dynamic graph algorithms verification and synthesis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：