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

A Faster and Simpler Fully dynamic Transitive Closure

ACM TRANSACTIONS ON algorithms 2008年第1期4卷 6-6页

作者： 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

来源：评论

学校读者我要写书评

暂无评论

DECREMENTAL STRONGLY CONNECTED COMPONENTS AND SINGLE-SOURCE REACHABILITY IN NEAR-LINEAR TIME

引用

SIAM JOURNAL ON COMPUTING 2023年第2期52卷 STOC19-128-STOC19-155页

作者： Bernstein, Aaron Gutenberg, Maximilian Probst Wulff-Nilsen, Christian Rutgers Univ New Brunswick Dept Comp Sci Piscataway NJ 08854 USA Swiss Fed Inst Technol Dept Comp Sci Zurich Switzerland Univ Copenhagen Dept Comp Sci Copenhagen Denmark BARC Copenhagen Denmark

Computing the strongly connected Components (SCCs) in a graph G = (V, E) is known to take only O(m+n) time using an algorithm by Tarjan [SIAM J. Comput., 1 (1972), pp. 146-160] where m = vertical bar E vertical bar, n = vertical bar V vertical bar. For fully dynamic graphs, conditional lower bounds provide evidence that the update time cannot be improved by polynomial factors over recomputing the SCCs from scratch after every update. Nevertheless, substantial progress has been made to find algorithms with fast update time for decremental graphs, i.e., graphs that undergo edge deletions. In this paper, we present the first algorithm for general decremental graphs that maintains the SCCs in total update time (O) over tilde (m), thus only a polylogarithmic factor from the optimal running time. (We use (O) over tilde (f(n)) notation to suppress logarithmic factors, i.e., g(n) = (O) over tilde (f(n)) if g(n) = O(f(n)polylog(n)).) Our result also yields the fastest algorithm for the decremental single-source reachability (SSR) problem which can be reduced to decrementally maintaining SCCs. Using a well-known reduction, we use our decremental result to achieve new update/query-time trade-offs in the fully dynamic setting. We can maintain the reachability of pairs SxV, S subset of V in fully dynamic graphs with update time (O) over tilde (vertical bar S vertical bar m/t) and query time O(t) for all t is an element of [1, vertical bar S vertical bar];this matches to polylogarithmic factors the best all-pairs reachability algorithm for S = V

关键词： dynamic graph algorithms data structures strongly connected components single-source reachability reachability ES-tree

来源：评论

学校读者我要写书评

暂无评论

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

引用

JOURNAL OF THE ACM 2014年第3期61卷 15-15页

作者： 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

来源：评论

学校读者我要写书评

暂无评论

All Maximal Independent Sets and dynamic Dominance for Sparse graphs

引用

ACM TRANSACTIONS ON algorithms 2009年第4期5卷 1–14页

作者： Eppstein, David Univ Calif Irvine Dept Comp Sci Irvine CA 92697 USA

We describe algorithms, based on Avis and Fukuda's reverse search paradigm, for listing all maximal independent sets in a sparse graph in polynomial time and delay per output. For bounded degree graphs, our algorithms take constant time per set generated;for minor-closed graph families, the time is O(n) per set, and for more general sparse graph families we achieve subquadratic time per set. We also describe new data structures for maintaining a dynamic vertex set S in a sparse or minor-closed graph family, and querying the number of vertices not dominated by S;for minor-closed graph families the time per update is constant, while it is sublinear for any sparse graph family. We can also maintain a dynamic vertex set in an arbitrary m-edge graph and test the independence of the maintained set in time O(root m) per update. We use the domination data structures as part of our enumeration algorithms.

关键词： Combinatorial enumeration reverse search maximal independent sets dominating sets dynamic graph algorithms bounded degree graphs sparse graphs minor-closed graph families

来源：评论

学校读者我要写书评

暂无评论

Constant-time dynamic weight approximation for minimum spanning forest

引用

INFORMATION AND COMPUTATION 2021年 281卷 104805-104805页

作者： Henzinger, Monika Peng, Pan Univ Vienna Fac Comp Sci Vienna Austria Univ Sci & Technol China Sch Comp Sci & Technol Hefei Peoples R China

We give two fully dynamic algorithms that maintain a (1 + epsilon)-approximation of the weight M of a minimum spanning forest (MSF) of an n-node graph G with edges weights in [1, W], for any epsilon > 0. (1) Our deterministic algorithm takes O(W2 log W /epsilon(3)) worst-case update time, which is O (1) if both W and E are constants. (2) Our randomized (Monte -Carlo style) algorithm works with high probability and runs in worst-case O (log W /epsilon(4)) update time if W = O((m*)(1/6)/log(2/3) n), where m* is the minimum number of edges in the graph throughout all the updates. It works even against an adaptive adversary. We complement our algorithmic results with two cell-probe lower bounds for dynamically maintaining an approximation of the weight of an MSF of a graph. (C) 2021 Elsevier Inc. All rights reserved.

关键词： dynamic graph algorithms Minimum spanning forest Sublinear-time algorithms Cell-probe lower bounds

来源：评论

学校读者我要写书评

暂无评论

Fully dynamic algorithms for Chordal graphs and Split graphs

引用

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

作者： Ibarra, Louis Depaul Univ Sch Comp Chicago IL 60604 USA

We present the first dynamic algorithm that maintains a clique tree representation of a chordal graph and supports the following operations: (1) query whether deleting or inserting an arbitrary edge preserves chordality;and (2) delete or insert an arbitrary edge, provided it preserves chordality. We give two implementations. In the first, each operation runs in O(n) time, where n is the number of vertices. In the second, an insertion query runs in O(log(2) n) time, an insertion in O(n) time, a deletion query in O(n) time, and a deletion in O(n log n) time. We also present a data structure that allows a deletion query to run in O(root m) time in either implementation, where m is the current number of edges. Updating this data structure after a deletion or insertion requires O(m) time. We also present a very simple dynamic algorithm that supports each of the following operations in O(1) time on a general graph: (1) query whether the graph is split, and (2) delete or insert an arbitrary edge.

关键词： dynamic graph algorithms chordal graphs clique trees split graphs

来源：评论

学校读者我要写书评

暂无评论

Fully dynamic (Δ+1)-Coloring in O(1) Update Time

引用

ACM TRANSACTIONS ON algorithms 2022年第2期18卷 10-10页

作者： Bhattacharya, Sayan Grandoni, Fabrizio Kulkarni, Janardhan Liu, Quanquan C. Solomon, Shay Univ Warwick Coventry CV4 7AL W Midlands England Polo Univ Lugano IDSIA USI SUPSI Campus EstVia La Santa 1 CH-6962 Lugano Switzerland Microsoft Res One Microsoft Way Redmond WA 98052 USA MIT CSA1L 32 Vassar St Cambridge MA 02139 USA Tel Aviv Univ POB 39040 IL-6997801 Tel Aviv Israel

The problem of (Delta+1)-vertex coloring a graph of maximum degree Delta has been extremely well studied over the years in various settings and models. Surprisingly, for the dynamic setting, almost nothing was known until recently. In SODA'18, Bhattacharya, Chakrabarty, Henzinger and Nanongkai devised a randomized algorithm for maintaining a (Delta + 1)-coloring with O(log Delta) expected amortized update time. In this article, we present an improved randomized algorithm for (Delta + 1)-coloring that achieves O(1) amortized update time and show that this bound holds not only in expectation but also with high probability. Our starting point is the state-of-the-art randomized algorithm for maintaining a maximal matching (Solomon, FOCS'16). We carefully build on the approach of Solomon, but, due to inherent differences between the maximal matching and (Delta + 1)-coloring problems, we need to deviate significantly from it in several crucial and highly nontrivial points.

关键词： graph coloring dynamic graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Fully dynamic MIS in Uniformly Sparse graphs

引用

ACM TRANSACTIONS ON algorithms 2020年第2期16卷 26-26页

作者： Onak, Krzysztof Schieber, Baruch Solomon, Shay Wein, Nicole IBM Res Yorktown Hts NY 10598 USA IBM Corp 1101 Kitchawan Rd Yorktown Hts NY 10598 USA New Jersey Inst Technol Newark NJ 07102 USA Tel Aviv Univ POB 39040 IL-6997801 Tel Aviv Israel MIT 77 Massachusetts Ave Cambridge MA 02139 USA

We consider the problem of maintaining a maximal independent set in a dynamic graph subject to edge insertions and deletions. Recently, Assadi et al. (at STOC'18) showed that a maximal independent set can be maintained in sublinear (in the dynamically changing number of edges) amortized update time. In this article, we significantly improve the update time for uniformly sparse graphs. Specifically, for graphs with arboricity a, the amortized update time of our algorithm is O(alpha(2) center dot log(2) n), where n is the number of vertices. For low arboricity graphs, which include, for example, minor-free graphs and some classes of "real-world" graphs, our update time is polylogarithmic. Our update time improves the result of Assadi et al. for all graphs with arboricity bounded by m(3/8-epsilon), for any constant epsilon > 0. This covers much of the range of possible values for arboricity, as the arboricity of a general graph cannot exceed m(1/2).

关键词： Maximal independent set dynamic graph algorithms graph arboricity edge orientations

来源：评论

学校读者我要写书评

暂无评论

Rethinking Incremental and Parallel Pointer Analysis

引用

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS 2019年第1期41卷 6-6页

作者： Liu, Bozhen Huang, Jeff Rauchwerger, Lawrence Texas A&M Univ College Stn TX 77843 USA

Pointer analysis is at the heart of most interprocedural program analyses. However, scaling pointer analysis to large programs is extremely challenging. In this article, we study incremental pointer analysis and present a new algorithm for computing the points-to information incrementally (i.e., upon code insertion, deletion, and modification). Underpinned by new observations of incremental pointer analysis, our algorithm significantly advances the state of the art in that it avoids redundant computations and the expensive graph reachability analysis, and preserves precision as the corresponding whole program exhaustive analysis. Moreover, it is parallel within each iteration of fixed-point computation. We have implemented our algorithm, IPA, for Java based on the WALA framework and evaluated its performance extensively on real-world large, complex applications. Experimental results show that IPA achieves more than 200X speedups over existing incremental algorithms, two to five orders of magnitude faster than whole program pointer analysis, and also improves the performance of an incremental data race detector by orders of magnitude. Our IPA implementation is open source and has been adopted by WALA.

关键词： Incremental pointer analysis parallelization dynamic graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Journey Planning algorithms for Massive Delay-Prone Transit Networks

引用

algorithms 2020年第1期13卷 2页

作者： D'Emidio, Mattia Khan, Imran Frigioni, Daniele Univ LAquila Dept Informat Engn Comp Sci & Math Via Vetoio I-67100 Laquila Italy GSSI Viale Francesco Crispi I-67100 Laquila Italy

This paper studies the journey planning problem in the context of transit networks. Given the timetable of a schedule-based transportation system (consisting, e.g., of trains, buses, etc.), the problem seeks journeys optimizing some criteria. Specifically, it seeks to answer natural queries such as, for example, "find a journey starting from a source stop and arriving at a target stop as early as possible". The fastest approach for answering to these queries, yielding the smallest average query time even on very large networks, is the Public Transit Labeling framework, proposed for the first time in Delling et al., SEA 2015. This method combines three main ingredients: (i) a graph-based representation of the schedule of the transit network;(ii) a labeling of such graph encoding its transitive closure (computed via a time-consuming pre-processing);(iii) an efficient query algorithm exploiting both (i) and (ii) to answer quickly to queries of interest at runtime. Unfortunately, while transit networks' timetables are inherently dynamic (they are often subject to delays or disruptions), ptl is not natively designed to handle updates in the schedule-even after a single change, precomputed data may become outdated and queries can return incorrect results. This is a major limitation, especially when dealing with massively sized inputs (e.g., metropolitan or continental sized networks), as recomputing the labeling from scratch, after each change, yields unsustainable time overheads that are not compatible with interactive applications. In this work, we introduce a new framework that extends ptl to function in delay-prone transit networks. In particular, we provide a new set of algorithms able to update both the graph and the precomputed labeling whenever a delay affects the network, without performing any recomputation from scratch. We demonstrate the effectiveness of our solution through an extensive experimental evaluation conducted on real-world networks. Our experiments

关键词： journey planning transit networks dynamic graph algorithms algorithms engineering massive datasets experimental algorithmics

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：