Near-optimal fully-dynamic graph connectivity
DOI10.1145/335305.335345zbMATH Open1296.05110OpenAlexW2010151376WikidataQ55966918 ScholiaQ55966918MaRDI QIDQ3192002FDOQ3192002
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
Recommendations
- Faster deterministic fully-dynamic graph connectivity
- Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
- Lower bounds for fully dynamic connectivity problems in graphs
- Randomized fully dynamic graph algorithms with polylogarithmic time per operation
- Improved data structures for fully dynamic biconnectivity
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40)
Cited In (43)
- An efficient algorithm for batch stability testing
- Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
- Dynamic connectivity in disk graphs
- Dynamic connectivity for axis-parallel rectangles
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
- Discovering recurring activity in temporal networks
- Efficient algorithms for computing Reeb graphs
- An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms
- Space-efficient Euler partition and bipartite edge coloring
- Approximating multistage matching problems
- A fast algorithm for connectivity graph approximation using modified Manhattan distance in dynamic networks
- Fast compatibility testing for rooted phylogenetic trees
- Fully Dynamic Algorithms for 2-Edge Connectivity
- Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time
- Approximating multistage matching problems
- Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics
- Decremental SPQR-trees for Planar Graphs
- Title not available (Why is that?)
- A topological approach to dynamic graph connectivity
- On dynamic bit-probe complexity
- Good \(r\)-divisions imply optimal amortized decremental biconnectivity
- A new approach for the multiobjective minimum spanning tree
- The saga of minimum spanning trees
- On the König deficiency of zero-reducible graphs
- An algorithm for computing simple \(k\)-factors
- Random-cluster dynamics on random regular graphs in tree uniqueness
- Computing the map of geometric minimal cuts
- Constant-time dynamic weight approximation for minimum spanning forest
- Deterministic Fault-Tolerant Connectivity Labeling Scheme
- Faster Fully-Dynamic Minimum Spanning Forest
- A deterministic \(O(m \log {m})\) time algorithm for the Reeb graph
- Optimal offline dynamic \(2\), \(3\)-edge/vertex connectivity
- Improved dynamic colouring of sparse graphs
- Optimal decremental connectivity in planar graphs
- Space-Efficient Euler Partition and Bipartite Edge Coloring
- Computing large planar regions in terrains, with an application to fracture surfaces
- Computing Large Planar Regions in Terrains
- Dynamic graph connectivity in polylogarithmic worst case time
- Listing the bonds of a graph in \(\widetilde{O} (n)\)-delay
- Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning
- Tree compatibility, incomplete directed perfect phylogeny, and dynamic graph connectivity: an experimental study
- Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs
This page was built for publication: Near-optimal fully-dynamic graph connectivity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3192002)
