Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
From MaRDI portal
Publication:5441357
DOI10.1145/502090.502095zbMath1127.68408WikidataQ55951524 ScholiaQ55951524MaRDI QIDQ5441357
Kristian de Lichtenberg, Jacob Holm, Mikkel Thorup
Publication date: 11 February 2008
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/502090.502095
90C35: Programming involving graphs or networks
68W40: Analysis of algorithms
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Fully Dynamic Maximal Matching in $O(\log n)$ Update Time (Corrected Version), Unnamed Item, Unnamed Item, Dynamic Approximate Vertex Cover and Maximum Matching, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time, Least resolved trees for two-colored best match graphs, Decremental SPQR-trees for Planar Graphs, Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs, Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier, Fully Dynamic Maximal Matching in $O(\log n)$ Update Time, A consistent semantics of self-adjusting computation, Unnamed Item, Dynamic graph coloring, A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges, Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs., Fast and Deterministic Approximations for k-Cut., Reoptimization of maximum weight induced hereditary subgraph problems, Connectivity games over dynamic networks, The \(O(n)\) loop model on a three-dimensional lattice, The saga of minimum spanning trees, Computing the map of geometric minimal cuts, Worm Monte Carlo study of the honeycomb-lattice loop model, \(f\)-sensitivity distance oracles and routing schemes, New results on optimizing rooted triplets consistency, The binary perfect phylogeny with persistent characters, Fast compatibility testing for rooted phylogenetic trees, Incomplete directed perfect phylogeny in linear time, Upper and lower bounds for fully retroactive graph problems, Dynamic shortest paths and transitive closure: algorithmic techniques and data structures, Inferring a level-1 phylogenetic network from a dense set of rooted triplets, Efficient algorithms for computing Reeb graphs, Algorithms for computing a parameterized \(st\)-orientation, Dynamic bottleneck optimization for \(k\)-edge and 2-vertex connectivity, Maintaining dynamic minimum spanning trees: an experimental study, Dynamic mechanism design, Dynamic connectivity for axis-parallel rectangles, Optimal decremental connectivity in planar graphs, On the coupling time of the heat-bath process for the Fortuin-Kasteleyn random-cluster model, New heuristics for rooted triplet consistency, Discovering recurring activity in temporal networks, The matroid structure of representative triple sets and triple-closure computation, Reconstructing gene trees from Fitch's xenology relation, General compact labeling schemes for dynamic trees, A fully dynamic graph algorithm for recognizing interval graphs, An efficient algorithm for batch stability testing, Constant-time dynamic weight approximation for minimum spanning forest, Single-source shortest paths and strong connectivity in dynamic planar graphs, Multiple-edge-fault-tolerant approximate shortest-path trees, Approximating dynamic weighted vertex cover with soft capacities, Dynamic kernels for hitting sets and set packing, Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications, Percolation on complex networks: theory and application, Work-sensitive dynamic complexity of formal languages, Tree compatibility, incomplete directed perfect phylogeny, and dynamic graph connectivity: an experimental study, Combining SAT solvers with computer algebra systems to verify combinatorial conjectures, How to use spanning trees to navigate in graphs, A deterministic \(O(m \log {m})\) time algorithm for the Reeb graph, Incremental algorithm for maintaining a DFS tree for undirected graphs, Fully dynamic all pairs shortest paths with real edge weights, Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning, Trade-offs in dynamic coloring for bipartite and general graphs, Randomization for Efficient Dynamic Graph Algorithms, Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization, Algorithmic Techniques for Maintaining Shortest Routes in Dynamic Networks, A Game Theoretic Approach to the Analysis of Dynamic Networks, A survey on combinatorial optimization in dynamic environments, On Dynamic DFS Tree in Directed Graphs, Time Windowed Data Structures for Graphs, How to Use Spanning Trees to Navigate in Graphs, Connectivity Oracles for Graphs Subject to Vertex Failures, Faster Fully-Dynamic Minimum Spanning Forest, MathCheck: A Math Assistant via a Combination of Computer Algebra Systems and SAT Solvers
