1,720,998 research outputs found
Maintaining the 3-edge-connected components of a graph on-line
No full textThe problem of maintaining the 3-edge-connected components of a graph undergoing repeated dynamic modifications, such as edge and vertex insertions, is studied. This paper shows how to answer the question of whether or not two vertices belong to the same 3-edge-connected component of a connected graph that is undergoing only edge insertions. Any sequence of q query and updates on an n-vertex graph can be performed in time
Fully dynamic algorithms for 2-edge connectivity
No full textThis paper studies the problem of maintaining the 2-edge-connected components of a graph undergoing repeated dynamic modifications, such as edge insertions and edge deletions. It is shown how to test at any time whether two vertices belong to the same 2-edge-connected component, and how to insert and delete an edge in time in the worst case, where m is the current number of edges in the graph
Sparse dynamic programming I: linear cost functions
No full textDynamic programming solutions to a number of different recurrence equations for sequence comparison and for RNA secondary structure prediction are considered. These recurrences are defined over a number of points that is quadratic in the input size; however only a sparse set matters for the result. Efficient algorithms for these problems are given, when the weight functions used in the recurrences are taken to be linear. The time complexity of the algorithms depends almost linearly on the number of points that need to be considered; when the problems are sparse this results in a substantial speed-up over known algorithms
Sparsification: A technique for speeding up dynamic graph algorithms
No full textWe provide data structures that maintain a graph as edges are inserted and deleted, and
keep track of the following properties with the following times: minimum spanning forests, graph
connectivity, graph 2-edge connectivity, and bipartiteness in time O(n1/2) per change; 3-edge
connectivity, in time O(n2/3) per change; 4-edge connectivity, in time O(na(n)) per change; k-edge
connectivity for constant k, in time O(nlogn) per change; 2-vertex connectivity, and 3-vertex
connectivity, in time O(n) per change; and 4-vertex connectivity, in time O(na(n)) per change
Separator based sparsification II: edge and vertex connectivity
No full textWe consider the problem of maintaining a dynamic planar graph subject to edge insertions and edge deletions that preserve planarity but that can change the embedding. We describe algorithms and data structures for maintaining information about 2- and 3-vertex-connectivity, and 3- and 4-edge-connectivity in a planar graph in O(n1/2) amortized time per insertion, deletion, or connectivity query. All of the data structures handle insertions that keep the graph planar without regard to any particular embedding of the graph. Our algorithms are based on a new type of sparsification combined with several properties of separators in planar graphs
- …
