Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
Published 1 January 1998Open access
Jacob Holm, Kristian de Lichtenberg, Mikkel Thorup
Citations71
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Deterministic fully dynamic graph algorithms are presented for connectivity, minimum spanning tree, 2-edge connectivity, and biconnectivity.
Abstract
Deterministic fully dynamic graph algorithms are presented for connectivity, minimum spanning forest, a-edge connectivity, and biconnectivity. Assuming that we start with no edges in a graph with n vertices, the amortized operation cost0 arc O(log2 n) for connectivity and O(log4 n) for minimum spanning forest, 2+dgeconnectivity, and biconnectity.
Keywords
Computer Science
Journal of Computer and System SciencesA data structure for dynamic trees
1,040 Citations1983Daniel D. Sleator, Robert E. Tarjan
SIAM Journal on ComputingData Structures for On-Line Updating of Minimum Spanning Trees, with Applications
380 Citations1985Greg N. Frederickson
Data structures are presented for the problem of maintaining a minimum spanning tree on-line under the operation of updating the cost of some edge in the graph.
Journal of the ACMSparsification—a technique for speeding up dynamic graph algorithms
290 Citations1997David Eppstein, Zvi Galil +2 more
All algorithms are based on a new technique that transforms an algorithm for sparse graphs into one that will work on any graph, which is calledsparsification, and results speed up the insertion times to match the bounds of known partially dynamic algorithms.
Journal of the ACMRandomized fully dynamic graph algorithms with polylogarithmic time per operation
285 Citations1999Monika Henzinger, Valerie King
The first fully dynamic algorithms that maintain connectivity, bipartiteness, and approximate minimum spanning trees in polylogarithmic time per edge insertion or deletion are presented.
Journal of the ACMAn On-Line Edge-Deletion Problem
283 Citations1981Yossi Shiloach, Shimon Even
An algorithm is presented which maintains a data structure in which each question is answered in constant time and for which the total time involved in answering q questions and maintaining the data structure is O(q + I VI) lED.
Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs
227 Citations2003Valerie King
The first fully dynamic algorithms for maintaining all-pairs shortest paths in digraphs with positive integer weights less than b are presented, which use simple data structures, and are deterministic.
SIAM Journal on ComputingBiased Search Trees
146 Citations1985Samuel W. Bent, Daniel D. Sleator +1 more
Two related classes of biased search trees whose average access time is within a constant factor of the minimum and that are easy to update under insertions, deletions and more radical update operations are described.
Data structures for on-line updating of minimum spanning trees
141 Citations1983Greg N. Frederickson
Data structures are presented for the problem of maintaining a minimum spanning tree on-line under the operation of updating the cost of some edge in the graph.
Fully dynamic biconnectivity and transitive closure
135 Citations2002Monika Henzinger, Valerie King
This paper presents the first dynamic algorithm that answers biconnectivity queries in time O(log/sup 2/n) in a n-node graph and can be updated after an edge insertion or deletion in polylogarithmic time.
AlgorithmicaMaintaining bridge-connected and biconnected components on-line
135 Citations1992Jeffery Westbrook, Robert E. Tarjan
A modified version of the dynamic trees of Sleator and Tarjan is developed that is suitable for efficient recursive algorithms, and used to reduce the running time of the algorithms for both problems toO(mα(m,n), where α is a functional inverse of Ackermann's function.
AlgorithmicaConstructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology
114 Citations1999Monika Henzinger, Valerie King +1 more
Two algorithms which test if a given set of trees has a consensus tree and if so, construct one are presented and two applications of these consensus tree algorithms which solve other problems in computational evolutionary biology are presented.
Randomized dynamic graph algorithms with polylogarithmic time per operation
110 Citations1995Monika Henzinger, Valerie King
This paper presents the first fully dynamic algorithms that maintain connectivity, bipartiteness, and approximate minimum spanning trees in polylogarithmic time per edge insertion or deletion using a new dynamic technique that combines a novel graph decomposition with randomization.
Theoretical Computer ScienceComplexity models for incremental computation
105 Citations1994Peter Bro Miltersen, Sairam Subramanian +2 more
This work defines complexity classes that capture the intuitive notion of incremental efficiency and study their relation to existing complexity classes and shows that problems that have small sequential space complexity also have small incremental time complexity.
SIAM Journal on ComputingAmbivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees
102 Citations1997Greg N. Frederickson
Ambivalent data structures for dynamic 2-edge-connectivity and k smallest spanning trees
100 Citations2002Greg N. Frederickson
Ambivalent data structures are presented for several problems on undirected graphs and used in finding the k smallest spanning trees of a weighted undirecting graph in O(m log beta (m,n)+min(k/sup 3/2/, km/sup 1/2/)) time, where m and n are understood to be the current number of edges and vertices, respectively.
Discrete & Computational GeometryDynamic Euclidean minimum spanning trees and extrema of binary functions
90 Citations1995David Eppstein
This work maintains the minimum spanning tree of a point set in the plane subject to point insertions and deletions, in amortized timeO(n1/2 log2n) per update operation, and uses a novel construction, theordered nearest neighbor path of a set of points.
Lecture notes in computer scienceMaintaining minimum spanning trees in dynamic graphs
84 Citations1997Monika Henzinger, Valerie King
This work presents the first fully dynamic deterministic algorithm for maintaining connectivity and, bipartiteness in amortized time O(n 1/3 log n) per update, with O(1) worst case time per query.
Journal of AlgorithmsEfficient Algorithms for Petersen's Matching Theorem
70 Citations2001Thérèse Biedl, Prosenjit Bose +2 more
An O(nlog4n)-time algorithm for perfect matching in a 3-regular bridgeless graph and three applications of this result are presented: terrain guarding, adaptive mesh refinement, and quadrangulation.
AlgorithmicaLower Bounds for Fully Dynamic Connectivity Problems in Graphs
66 Citations1998Monika Henzinger, Michael L. Fredman
An amortized lower bound of $\Omega$ (log n / {k (log log n} + log b)) per edge insertion, deletion, or query operation in the cell probe model is shown, which are the first lower bounds for fully dynamic connectivity problems.
Lecture notes in computer scienceMinimizing diameters of dynamic trees
61 Citations1997Stephen Alstrup, Jacob Holm +2 more
This paper considers an on-line problem related to minimizing the diameter of a dynamic tree T, and shows how each such best swap can be found in worst-case O(log2n) time.
Random Structures and AlgorithmsSampling to provide or to bound: With applications to fully dynamic graph algorithms
49 Citations1997Monika Henzinger, Mikkel Thorup
This work gives an optimal algorithm for providing an upper bound on the size of R that holds with high probability and improves the time per operation for various dynamic graph algorithms by a factor of O(log n).
Fully dynamic biconnectivity in graphs
39 Citations1992Monika Rauch
The author presents an algorithm for maintaining the bi-connected components of a graph during a sequence of edge insertions and deletions, which is the first sublinear algorithm for this problem.
Journal of AlgorithmsDecremental Dynamic Connectivity
39 Citations1999Mikkel Thorup
It is shown that starting from a graph with m edges and n nodes, it can maintain a spanning forest during m deletions in O ( m log) expected time, which is based on a general randomized reduction for edge connectivity problems of many deletions-only queries to a few deletions and insertions queries.
Improved data structures for fully dynamic biconnectivity
39 Citations1994Monika Rauch
The algorithm for general graphs can also find the biconnected components of all vertices in time $O(n)$ and the update times in general graphs are amortized, showing that the biconsnected component of a graph can be dynamically maintained almost as efficiently as the connected components.
AlgorithmicaFully dynamic biconnectivity in graphs
25 Citations1995Monika Henzinger
Any query of the form ‘Are the verticesu andv biconnected?’ can be answered in timeO(1) and this is the first sublinear algorithm for this problem.
Lecture notes in computer scienceCertificates and fast algorithms for biconnectivity in fully-dynamic graphs
22 Citations1995Monika Henzinger, Han La Poutré
This paper obtains fully-dynamic algorithms for biconnectivity in graphs that run in O(√n log n log⌈m/n⌉) amortized time per operation, where m is the number of edges and n is theNumber of nodes in the graph.
SIAM Journal on ComputingAlgorithms and Data Structures for an Expanded Family of Matroid Intersection Problems
16 Citations1989Greg N. Frederickson, Mandayam A. Srinivas
A characterization is presented for how the solution changes when one element changes in cost, and efficient update algorithms are given for maintaining a color-constrained minimum spanning tree in either a general or a planar graph.
Fully Dynamic 2-Edge Connectivity Algorithm in Polylogarithmic Time per Operation
12 Citations1997Monika Henzinger, Valerie King
This paper presents the first dynamic algorithm that maintains 2-edge connectivity in polylogarithmic time per operation, a Las-Vegas type randomized algorithm.