Near-optimal fully-dynamic graph connectivity
From MaRDI portal
Publication:3192002
DOI10.1145/335305.335345zbMath1296.05110OpenAlexW2010151376WikidataQ55966918 ScholiaQ55966918MaRDI QIDQ3192002
Publication date: 26 September 2014
Published in: Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/335305.335345
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)
Related Items (34)
Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Space-Efficient Euler Partition and Bipartite Edge Coloring ⋮ Space-efficient Euler partition and bipartite edge coloring ⋮ On dynamic bit-probe complexity ⋮ Faster Fully-Dynamic Minimum Spanning Forest ⋮ A new approach for the multiobjective minimum spanning tree ⋮ A deterministic \(O(m \log {m})\) time algorithm for the Reeb graph ⋮ Listing the bonds of a graph in \(\widetilde{O} (n)\)-delay ⋮ Optimal decremental connectivity in planar graphs ⋮ Dynamic connectivity in disk graphs ⋮ Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs ⋮ Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics ⋮ Deterministic Fault-Tolerant Connectivity Labeling Scheme ⋮ An efficient algorithm for batch stability testing ⋮ The saga of minimum spanning trees ⋮ Efficient algorithms for computing Reeb graphs ⋮ Computing the map of geometric minimal cuts ⋮ Discovering recurring activity in temporal networks ⋮ Decremental SPQR-trees for Planar Graphs ⋮ Computing Large Planar Regions in Terrains ⋮ An algorithm for computing simple \(k\)-factors ⋮ Fast compatibility testing for rooted phylogenetic trees ⋮ Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning ⋮ On the König deficiency of zero-reducible graphs ⋮ Approximating multistage matching problems ⋮ Approximating multistage matching problems ⋮ Random-cluster dynamics on random regular graphs in tree uniqueness ⋮ Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs ⋮ Constant-time dynamic weight approximation for minimum spanning forest ⋮ Dynamic connectivity for axis-parallel rectangles ⋮ Tree compatibility, incomplete directed perfect phylogeny, and dynamic graph connectivity: an experimental study ⋮ Computing large planar regions in terrains, with an application to fracture surfaces ⋮ Unnamed Item ⋮ Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time
This page was built for publication: Near-optimal fully-dynamic graph connectivity
