We initiate the study of fast dynamicalgorithms for graph sparsification problems and obtain fully dynamicalgorithms, allowing both edge insertions and edge deletions, that take polylogarithmic time after each updat...
详细信息
ISBN:
(纸本)9781509039333
We initiate the study of fast dynamicalgorithms for graph sparsification problems and obtain fully dynamicalgorithms, allowing both edge insertions and edge deletions, that take polylogarithmic time after each update in the graph. Our three main results are as follows. First, we give a fully dynamic algorithm for maintaining a (1 +/-epsilon)-spectral sparsifier with amortized update time poly(log n, epsilon(-1)). Second, we give a fully dynamic algorithm for maintaining a (1 +/-epsilon)-cut sparsifier with worst-case update time poly(log n, epsilon(-1)). Both sparsifiers have size n. poly(log n, epsilon(-1)). Third, we apply our dynamic sparsifier algorithm to obtain a fully dynamic algorithm for maintaining a (1 - epsilon)-approximation to the value of the maximum flow in an unweighted, undirected, bipartite graph with amortized update time poly(log n, epsilon(-1)).
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...
详细信息
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.
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 grap...
详细信息
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.
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 randomiz...
详细信息
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
Betweenness centrality quantifies the importance of nodes in a graph in many applications, including network analysis, community detection and identification of influential users. Typically, graphs in such application...
详细信息
Betweenness centrality quantifies the importance of nodes in a graph in many applications, including network analysis, community detection and identification of influential users. Typically, graphs in such applications evolve over time. Thus, the computation of betweenness centrality should be performed incrementally. This is challenging because updating even a single edge may trigger the computation of all-pairs shortest paths in the entire graph. Existing approaches cannot scale to large graphs: they either require excessive memory (i.e., quadratic to the size of the input graph) or perform unnecessary computations rendering them prohibitively slow. We propose iCENTRAL;a novel incremental algorithm for computing betweenness centrality in evolving graphs. We decompose the graph into biconnected components and prove that processing can be localized within the affected components. iCENTRAL is the first algorithm to support incremental betweeness centrality computation within a graph component. This is done efficiently, in linear space;consequently, iCENTRAL scales to large graphs. We demonstrate with real datasets that the serial implementation of iCENTRAL is up to 3.7 times faster than existing serial methods. Our parallel implementation that scales to large graphs, is an order of magnitude faster than the state-of-the-art parallel algorithm, while using an order of magnitude less computational resources.
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 ins...
详细信息
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))).
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...
详细信息
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.
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 a...
详细信息
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.
In this paper we introduce a general framework for casting fully dynamic transitive closure into the problem of reevaluating polynomials over matrices. With this technique, we improve the best known bounds for fully d...
详细信息
In this paper we introduce a general framework for casting fully dynamic transitive closure into the problem of reevaluating polynomials over matrices. With this technique, we improve the best known bounds for fully dynamic transitive closure. In particular, we devise a deterministic algorithm for general directed graphs that achieves O(n(2)) amortized time for updates, while preserving unit worst-case cost for queries. In case of deletions only, our algorithm performs updates faster in O(n) amortized time. We observe that fully dynamic transitive closure algorithms with O(1) query time maintain explicitly the transitive closure of the input graph, in order to answer each query with exactly one lookup (on its adjacency matrix). Since an update may change as many as Omega(n(2)) entries of this matrix, no better bounds are possible for this class of algorithms.
We present fully dynamicalgorithms for maintaining the biconnected components in general and plane graphs. A fully dynamic algorithm maintains a graph during a sequence of insertions and deletions of edges or isolate...
详细信息
We present fully dynamicalgorithms for maintaining the biconnected components in general and plane graphs. A fully dynamic algorithm maintains a graph during a sequence of insertions and deletions of edges or isolated vertices. Let m be the number of edges and n be the number of vertices in a graph. The time per operation of the best deterministic algorithms is O(root n) in general graphs and O(log n) in plane graphs for fully dynamic connectivity and O(min{m(2/3), n}) in general graphs and O(root n) in plane graphs for fully dynamic biconnectivity. We improve the later running times to O(root m log n) in general graphs and O(log(2) n) in plane graphs. Our algorithm for general graphs can also nd the biconnected components of all vertices in time O(n).
暂无评论