Fully dynamic strongly connected components in planar digraphs
From MaRDI portal
Cites work
- A fully dynamic approximation scheme for shortest paths in planar graphs
- A new algorithm for optimal 2-constraint satisfaction and its implications
- A new approach to incremental cycle detection and related problems
- A strong-connectivity algorithm and its applications in data flow analysis
- Better tradeoffs for exact distance oracles in planar graphs
- Computing and Combinatorics
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Decremental single-source reachability and strongly connected components in \(\widetilde{O}(m \sqrt{n})\) total update time
- Decremental single-source reachability in planar digraphs
- Decremental strongly-connected components and single-source reachability in near-linear time
- Depth-First Search and Linear Graph Algorithms
- Deterministic decremental reachability, SCC, and shortest paths via directed expanders and congestion balancing
- Dynamic matrix inverse: improved algorithms and matching conditional lower bounds
- Dynamic Plane Transitive Closure
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Faster deterministic fully-dynamic graph connectivity
- Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
- Holiest minimum-cost paths and flows in surface graphs
- scientific article; zbMATH DE number 7788470 (Why is no real title available?)
- Improved deterministic algorithms for decremental reachability and strongly connected components
- Improved Dynamic Reachability Algorithms for Directed Graphs
- Incremental cycle detection, topological ordering, and strong component maintenance
- Incremental SCC maintenance in sparse graphs
- Multiple-source shortest paths in planar graphs
- On fully dynamic strongly connected components
- On the complexity of k-SAT
- Path-based depth-first search for strong and biconnected components
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Popular conjectures imply strong lower bounds for dynamic problems
- Single-source shortest paths and strong connectivity in dynamic planar graphs
- Structured recursive separator decompositions for planar graphs in linear time
- Submatrix maximum queries in Monge matrices and partial Monge matrices, and their applications
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
- Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
This page was built for publication: Fully dynamic strongly connected components in planar digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6875099)
