Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
From MaRDI portal
Publication:5874499
DOI10.4230/LIPIcs.ESA.2020.31OpenAlexW3081852366MaRDI QIDQ5874499
Panagiotis Charalampopoulos, Adam Karczmarz
Publication date: 7 February 2023
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/12897/pdf/LIPIcs-ESA-2020-31.pdf/
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On dynamic shortest paths problems
- A fully dynamic approximation scheme for shortest paths in planar graphs
- Separator based sparsification. I: Planarity testing and minimum spanning trees
- Faster approximate diameter and distance oracles in planar graphs
- Planar graphs, negative weight edges, shortest paths, and near linear time
- Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs
- Dynamic Approximate All-Pairs Shortest Paths: Breaking the $O(mn)$ Barrier and Derandomization
- Multiple-Source Shortest Paths in Embedded Graphs
- Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms
- Approximate Distance Oracles with Improved Bounds
- Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance
- Shortest path queries in planar graphs
- An O ( n log n ) algorithm for maximum st -flow in a directed planar graph
- Constant Query Time $$(1+\epsilon )$$ -Approximate Distance Oracle for Planar Graphs
- Dynamic Plane Transitive Closure
- Approximate distance oracles
- Worst-case update times for fully-dynamic all-pairs shortest paths
- Shortest Paths in Planar Graphs with Real Lengths in O(nlog2 n/loglogn) Time
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- An On-Line Edge-Deletion Problem
- Maintenance of a minimum spanning forest in a dynamic plane graph
- Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff
- On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs
- Fully dynamic all-pairs shortest paths with worst-case update-time revisited
- Deterministic Partially Dynamic Single Source Shortest Paths for Sparse Graphs
- Fully Dynamic Connectivity in O(log n(log log n)2) Amortized Expected Time
- Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
- Min st -Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time
- A New Approach to Incremental Cycle Detection and Related Problems
- Decremental single-source reachability in planar digraphs
- Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
- New algorithms and hardness for incremental single-source shortest paths in directed graphs
- Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler
- Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary
- Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds
- Almost optimal distance oracles for planar graphs
- Decremental strongly-connected components and single-source reachability in near-linear time
- A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems
- Holiest minimum-cost paths and flows in surface graphs
- Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
- Algorithm Theory - SWAT 2004
- Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
- Deterministic decremental single source shortest paths: beyond the o(mn) bound
- Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels
- Improved algorithms for min cut and max flow in undirected planar graphs
- A new approach to dynamic all pairs shortest paths
- Compact oracles for reachability and approximate distances in planar digraphs
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Structured recursive separator decompositions for planar graphs in linear time
- Computing and Combinatorics
- Approximate Distance Oracles with Improved Query Time
- More Compact Oracles for Approximate Distances in Undirected Planar Graphs
- Dynamic graph connectivity in polylogarithmic worst case time
- Faster Deterministic Fully-Dynamic Graph Connectivity
- Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
- Many distances in planar graphs
This page was built for publication: Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
