We obtain a new fully dynamic algorithm for the reachability problem in directed graphs. Our algorithm has an amortized update time of O(m + n log n) and a worst-case query time of O(n), where m is the current number ...
详细信息
We obtain a new fully dynamic algorithm for the reachability problem in directed graphs. Our algorithm has an amortized update time of O(m + n log n) and a worst-case query time of O(n), where m is the current number of edges in the graph, and n is the number of vertices in the graph. Each update operation either inserts a set of edges that touch the same vertex, or deletes an arbitrary set of edges. The algorithm is deterministic and uses fairly simple data structures. One of the ingredients used by this new algorithm may be interesting in its own right. It is a new dynamic algorithm for strong connectivity in directed graphs with an interesting "retrospectiveness" property. Each insert operation creates a new version of the graph. A delete operation deletes edges from all versions. Strong connectivity queries can be made on each version of the graph. The algorithm handles each update in O(m alpha(n)) amortized time, and each query in O(1) worst-case time, where alpha(n) is a functional inverse of Ackermann's function appearing in the analysis of the Union-Find data structure. Note that the update time of O(m alpha(n)), in the case of a delete operation, is the time needed for updating all versions of the graph.
We study the problem of maintaining a breadth-first spanning tree (BFS tree) in partially dynamic distributed networks modeling a sequence of either failures or additions of communication links (but not both). We pres...
详细信息
We study the problem of maintaining a breadth-first spanning tree (BFS tree) in partially dynamic distributed networks modeling a sequence of either failures or additions of communication links (but not both). We present deterministic (1 + is an element of)-approximation algorithms whose amortized time (over some number of link changes) is sublinear in D, the maximum diameter of the network. Our technique also leads to a deterministic (1 + is an element of)-approximate incremental algorithm for single-source shortest paths in the sequential (usual RAM) model. Prior to our work, the state of the art was the classic exact algorithm of Even and Shiloach (1981), which is optimal under some assumptions (Roditty and Zwick 2011;Henzinger et al. 2015). Our result is the first to show that, in the incremental setting, this bound can be beaten in certain cases if some approximation is allowed.
This work introduces Loop-Free Routing (LFR), a new loop-free distance-vector routing algorithm, which is able to update the shortest paths of a distributed network in fully dynamic scenarios. This work also provides ...
详细信息
This work introduces Loop-Free Routing (LFR), a new loop-free distance-vector routing algorithm, which is able to update the shortest paths of a distributed network in fully dynamic scenarios. This work also provides an evaluation based on simulations of LFR and Diffuse Update ALgorithm (DUAL), one of the most popular loop-free distance-vector algorithms, which is part of CISCO's widely used Enhanced Interior Gateway Routing Protocol (EIGRP). The simulations are performed on dynamic scenarios based on both real-world and controlled instances. The simulations show that LFR is always the best choice in terms of memory requirements, while in terms of messages sent LFR outperforms DUAL on real-world networks, whereas DUAL is the best choice on controlled scenarios. (C) 2013 Elsevier B.V. All rights reserved.
In this paper we consider the problem of dynamic transitive closure with lookahead. We present a randomized one-sided error algorithm with updates and queries in O(n(omega(1,1,epsilon)-epsilon)) time given a lookahead...
详细信息
In this paper we consider the problem of dynamic transitive closure with lookahead. We present a randomized one-sided error algorithm with updates and queries in O(n(omega(1,1,epsilon)-epsilon)) time given a lookahead of n(epsilon) operations, where omega(1,1,epsilon) is the exponent of multiplication of n x n matrix by n x n(epsilon) matrix. For epsilon <= 0.294 we obtain an algorithm with queries and updates in O(n(2-epsilon)) time, whereas for epsilon = 1 the time is O(n(omega-1)). This is essentially optimal as it implies an O(n(omega)) algorithm for boolean matrix multiplication. We also consider the offline transitive closure in planar graphs. For this problem, we show an algorithm that requires O(n(omega/2)) time to process n(1/2) operations. We also show a modification of these algorithms that gives faster amortized queries. Finally, we give faster algorithms for restricted type of updates, so called element updates. All of the presented algorithms are randomized with one-sided error. All our algorithms are based on dynamic algorithms with lookahead for matrix inverse, which are of independent interest.
We build upon the recent papers by Weinstein and Yu [11], Larsen [7], and Clifford et al. [3] to present a general framework that gives amortized lower bounds on the update and query times of dynamic data structures. ...
详细信息
We build upon the recent papers by Weinstein and Yu [11], Larsen [7], and Clifford et al. [3] to present a general framework that gives amortized lower bounds on the update and query times of dynamic data structures. Using our framework, we present two concrete results. 1. For the dynamic polynomial evaluation problem, where the polynomial is defined over a finite field of size n(l+Omega(1)) and has degree n, any dynamic data structure must either have an amortized update time of Omega((Ign/ IgIgn)(2)) or an amortized query time of Omega((lgn/IgIgn)(2)). 2. For the dynamic online matrix vector multiplication problem, where we get an n x n matrix whose entires are drawn from a finite field of size ne(1), any dynamic data structure must either have an amortized update time of Omega((lgn/ lgIgn)(2)) or an amortized query time of Omega(n . (Ign/ Ig Ign)(2)). For these two problems, the previous works by Larsen [7] and Clifford et al. [3] gave the same lower bounds, but only for worst case update and query times. Our bounds match the highest unconditional lower bounds known till date for any dynamic problem in the cell-probe model. (C) 2019 Elsevier B.V. All rights reserved.
Let M be a fixed finite monoid. We consider the problem of implementing a data type containing a vector x = (x(1), x(2),..., x(n)) is an element of M-n, initially (1, 1,..., 1), with two kinds of operations, for each ...
详细信息
Let M be a fixed finite monoid. We consider the problem of implementing a data type containing a vector x = (x(1), x(2),..., x(n)) is an element of M-n, initially (1, 1,..., 1), with two kinds of operations, for each i is an element of (1,..., n) and a is an element of M, an operation change(i,a), which changes x(i) to a and a single operation product returning IIi=1n x(i). This is the dynamic word problem for M. If we in addition for each j is an element of (1,..., n) have an operation prefix, returning IIi=1j x(i), we get the dynamic prefix problem for M. We analyze the complexity of these problems in the cell probe or decision assignment tree model for two natural cell sizes, 1 bit and log n bits. We obtain a partial classification of the complexity based on algebraic properties of M.
We obtain the following results related to dynamic versions of the shortest-paths problem: (i) Reductions that show that the incremental and decremental single-source shortest-paths problems, for weighted directed or ...
详细信息
We obtain the following results related to dynamic versions of the shortest-paths problem: (i) Reductions that show that the incremental and decremental single-source shortest-paths problems, for weighted directed or undirected graphs, are, in a strong sense, at least as hard as the static all-pairs shortest-paths problem. We also obtain slightly weaker results for the corresponding unweighted problems. (ii) A randomized fully-dynamic algorithm for the all-pairs shortest-paths problem in directed unweighted graphs with an amortized update time of (O) over tilde (m root n) (we use (O) over tilde to hide small poly-logarithmic factors) and a worst case query time is O(n(3/4)). (iii) A deterministic O(n(2)log n) time algorithm for constructing an O(log n)-spanner with O(n) edges for any weighted undirected graph on n vertices. The algorithm uses a simple algorithm for incrementally maintaining single-source shortest-paths tree up to a given distance.
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 adjacenc...
详细信息
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.
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 trapezoid...
详细信息
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.
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 inser...
详细信息
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.
暂无评论