Optimal decremental connectivity in planar graphs
From MaRDI portal
Publication:1693990
DOI10.1007/s00224-016-9709-xzbMath1379.05068OpenAlexW1771903244MaRDI QIDQ1693990
Publication date: 1 February 2018
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/4945/
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)
Cites Work
- Optimal on-line decremental connectivity in trees
- A class of algorithms which require nonlinear time to maintain disjoint sets
- Lower bounds for fully dynamic connectivity problems in graphs
- Efficient Union-Find for planar graphs and other sparse graph classes
- Separator based sparsification. I: Planarity testing and minimum spanning trees
- Lower bounds for the union-find and the split-find problem on pointer machines
- Decremental 2- and 3-connectivity on planar graphs
- Randomized fully dynamic graph algorithms with polylogarithmic time per operation
- Near-optimal fully-dynamic graph connectivity
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Maintenance of a minimum spanning forest in a dynamic plane graph
- Efficiency of a Good But Not Linear Set Union Algorithm
- Sparsification—a technique for speeding up dynamic graph algorithms
- Faster worst case deterministic dynamic connectivity
- Decremental Dynamic Connectivity
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Logarithmic Lower Bounds in the Cell-Probe Model
- Structured recursive separator decompositions for planar graphs in linear time
- Multiway Simple Cycle Separators and I/O-Efficient Algorithms for Planar Graphs
- Dynamic graph connectivity in polylogarithmic worst case time
- Faster Deterministic Fully-Dynamic Graph Connectivity
This page was built for publication: Optimal decremental connectivity in planar graphs
