Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
From MaRDI portal
Cites work
- scientific article; zbMATH DE number 432746 (Why is no real title available?)
- scientific article; zbMATH DE number 6850313 (Why is no real title available?)
- scientific article; zbMATH DE number 2119743 (Why is no real title available?)
- scientific article; zbMATH DE number 7204496 (Why is no real title available?)
- A fully dynamic approximation scheme for shortest paths in planar graphs
- A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems
- A new approach to dynamic all pairs shortest paths
- A new approach to incremental cycle detection and related problems
- Algorithm Theory - SWAT 2004
- Almost optimal distance oracles for planar graphs
- An On-Line Edge-Deletion Problem
- An O(n n) algorithm for maximum st-flow in a directed planar graph
- Approximate distance oracles
- Approximate distance oracles for planar graphs with improved query time-space tradeoff
- Approximate distance oracles with improved bounds
- Approximate distance oracles with improved query time
- Compact oracles for reachability and approximate distances in planar digraphs
- Computing and Combinatorics
- Constant query time \((1+\epsilon)\)-approximate distance oracle for planar graphs
- Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary
- Decremental single-source reachability in planar digraphs
- Decremental strongly-connected components and single-source reachability in near-linear time
- Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler
- Deterministic decremental single source shortest paths: beyond the \(O(mn)\) bound
- Deterministic partially dynamic single source shortest paths for sparse graphs
- Dynamic Plane Transitive Closure
- Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
- Dynamic graph connectivity in polylogarithmic worst case time
- Exact distance oracles for planar graphs
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Faster approximate diameter and distance oracles in planar graphs
- Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms
- Faster deterministic fully-dynamic graph connectivity
- Fully dynamic all-pairs shortest paths with worst-case update-time revisited
- Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels
- Fully dynamic connectivity in \(O(\log n(\log\log n)^2)\) amortized expected time
- Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds
- Holiest minimum-cost paths and flows in surface graphs
- Improved algorithms for \textsc{Min-cut} and \textsc{Max-flow} in undirected planar graphs
- Improved bounds for shortest paths in dense distance graphs
- Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
- Incremental cycle detection, topological ordering, and strong component maintenance
- Maintaining shortest paths under deletions in weighted directed graphs
- Maintenance of a minimum spanning forest in a dynamic plane graph
- Many distances in planar graphs
- Min \(st\)-cut oracle for planar graphs with near-linear preprocessing time
- More compact oracles for approximate distances in undirected planar graphs
- Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
- Multiple-source shortest paths in embedded graphs
- Multiple-source shortest paths in planar graphs
- New algorithms and hardness for incremental single-source shortest paths in directed graphs
- On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs
- On dynamic shortest paths problems
- 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
- Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
- Separator based sparsification. I: Planarity testing and minimum spanning trees
- Shortest path queries in planar graphs
- Shortest paths in directed planar graphs with negative lengths: a linear-space \(O(n\log^{2} n)\)-time algorithm
- Shortest paths in planar graphs with real lengths in \(O(n \log^{2} n/ \log \log n)\) time
- Structured recursive separator decompositions for planar graphs in linear time
- Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
- Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
- Worst-case update times for fully-dynamic all-pairs shortest paths
Cited in
(5)- Fine-grained complexity lower bounds for families of dynamic graphs
- On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs
- scientific article; zbMATH DE number 7204496 (Why is no real title available?)
- Fully dynamic algorithms for minimum weight cycle and related problems
- Single-source shortest paths and strong connectivity in dynamic planar graphs
This page was built for publication: Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874499)
