Near-optimal fully-dynamic graph connectivity
From MaRDI portal
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
Cited in
(54)- Dynamic connectivity for axis-parallel rectangles
- A topological approach to dynamic graph connectivity
- Lower bounds for fully dynamic connectivity problems in graphs
- Space-efficient Euler partition and bipartite edge coloring
- A new approach for the multiobjective minimum spanning tree
- Optimal decremental connectivity in planar graphs
- Discovering recurring activity in temporal networks
- Computing large planar regions in terrains, with an application to fracture surfaces
- An efficient algorithm for batch stability testing
- Random-cluster dynamics on random regular graphs in tree uniqueness
- Constant-time dynamic weight approximation for minimum spanning forest
- Optimal offline dynamic 2, 3-edge/vertex connectivity
- On the König deficiency of zero-reducible graphs
- Tree compatibility, incomplete directed perfect phylogeny, and dynamic graph connectivity: an experimental study
- On dynamic bit-probe complexity
- A deterministic \(O(m \log {m})\) time algorithm for the Reeb graph
- Efficient geo-graph contiguity and hole algorithms for geographic zoning and dynamic plane graph partitioning
- Faster Fully-Dynamic Minimum Spanning Forest
- Lower bounds for dynamic connectivity
- Fully Dynamic Algorithms for 2-Edge Connectivity
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
- The saga of minimum spanning trees
- Faster worst case deterministic dynamic connectivity
- Dynamic bridge-finding in \(\tilde{O}(\log^2 n)\) amortized time
- Computing the map of geometric minimal cuts
- Computing Large Planar Regions in Terrains
- Decremental SPQR-trees for Planar Graphs
- Decremental strongly connected components and single-source reachability in near-linear time
- Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
- Fully dynamic connectivity oracles under general vertex updates
- Space-Efficient Euler Partition and Bipartite Edge Coloring
- An Experimental Study of Polylogarithmic, Fully Dynamic, Connectivity Algorithms
- Dynamic graph connectivity in polylogarithmic worst case time
- Faster deterministic fully-dynamic graph connectivity
- scientific article; zbMATH DE number 7053292 (Why is no real title available?)
- Approximating multistage matching problems
- Approximating multistage matching problems
- Listing the bonds of a graph in \(\widetilde{O} (n)\)-delay
- 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
- Improved dynamic colouring of sparse graphs
- Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
- Good \(r\)-divisions imply optimal amortized decremental biconnectivity
- Deterministic fault-tolerant connectivity labeling scheme
- Good r-divisions imply optimal amortized decremental biconnectivity
- Fully-adaptive dynamic connectivity of square intersection graphs
- Fast compatibility testing for rooted phylogenetic trees
- Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity
- Efficient algorithms for computing Reeb graphs
- A fast algorithm for connectivity graph approximation using modified Manhattan distance in dynamic networks
- An algorithm for computing simple \(k\)-factors
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)
