Single-source shortest paths and strong connectivity in dynamic planar graphs
type: Item
instance of: scholarly article
title: Single-source shortest paths and strong connectivity in dynamic planar graphs
zbMATH Open document ID: 1485.68175
author: Panagiotis Charalampopoulos
author: Adam Karczmarz
published in: Journal of Computer and System Sciences
publication date: 2021-11-25T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/12897/
review text: The paper deals with the fully dynamic (both edge insertions and deletions, or reset of the source \(s\) of interest are allowed) single-source shortest paths problem for planar weighted digraphs. It is an extension of the static single-source shortest paths problem maintaining after edge insertions and deletions a data structure which supports shortest path queries originating in a fixed distinguished vertex. All known algorithms for the fully dynamic single-source shortest paths problem on general graphs are limited by the APSP conjecture: There exists no algorithm for solving the all-pairs shortest paths problem in general weighted graphs in time \(O(n^{3-\epsilon})\) for any constant \(\epsilon > 0\). Hence, no exact fully dynamic single-source shortest paths algorithms with \(O(n^{3-\epsilon})\) initialization time, \(O(m^{1-\epsilon})\) amortized update time and \(O(n^{1-\epsilon})\) query time at the same time is known (yet). However, restricting the attention to more structured graph classes and/or undirected graphs can give substantially better results. The main contribution of the paper results from focusing on planar weighted digraphs. The authors give a fully dynamic single-source shortest paths data structure for planar weighted digraphs with \(O(n^{4/5}\log^2 n)\) worst-case update time and \(O(\log^2 n)\) query time. The initialization time is \(O(n\log^2 n)\). This is the first fully dynamic strong-connectivity algorithm achieving both sublinear update time and polylogarithmic query time for the aforementioned class of digraphs.
reviewed by: Vladimír Lacko
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C22
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68P05
zbMATH DE Number: 7433356
zbMATH Keywords: dynamic graph algorithms
zbMATH Keywords: planar graphs
zbMATH Keywords: single-source shortest paths
zbMATH Keywords: strong connectivity
MaRDI profile type: Publication
OpenAlex ID: W3204093578
cites work: Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
cites work: A new approach to dynamic all pairs shortest paths
cites work: Algorithm Theory - SWAT 2004
cites work: Efficient Algorithms for Shortest Paths in Sparse Networks
cites work: Fully dynamic all-pairs shortest paths with worst-case update-time revisited
cites work: Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds
cites work: Worst-case update times for fully-dynamic all-pairs shortest paths
cites work: Q3138872
cites work: Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
cites work: An On-Line Edge-Deletion Problem
cites work: On dynamic shortest paths problems
cites work: New algorithms and hardness for incremental single-source shortest paths in directed graphs
cites work: Maintaining shortest paths under deletions in weighted directed graphs
cites work: Deterministic decremental single source shortest paths: beyond the o(mn) bound
cites work: Q5111375
cites work: Deterministic Partially Dynamic Single Source Shortest Paths for Sparse Graphs
cites work: A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems
cites work: Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler
cites work: Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary
cites work: Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
cites work: Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
cites work: Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
cites work: Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms
cites work: Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels
cites work: On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs
cites work: Planar graphs, negative weight edges, shortest paths, and near linear time
cites work: Submatrix Maximum Queries in Monge Matrices and Partial Monge Matrices, and Their Applications
cites work: Multiple-source shortest paths in planar graphs
cites work: A fully dynamic approximation scheme for shortest paths in planar graphs
cites work: Q4607877
cites work: Approximate Distance Oracles with Improved Bounds
cites work: Approximate Distance Oracles with Improved Query Time
cites work: Approximate distance oracles
cites work: Many distances in planar graphs
cites work: Shortest path queries in planar graphs
cites work: Q5743390
cites work: Almost optimal distance oracles for planar graphs
cites work: Q4607915
cites work: Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs
cites work: Q4829018
cites work: Compact oracles for reachability and approximate distances in planar digraphs
cites work: Constant Query Time $$(1+\epsilon )$$ -Approximate Distance Oracle for Planar Graphs
cites work: More Compact Oracles for Approximate Distances in Undirected Planar Graphs
cites work: Approximate Distance Oracles for Planar Graphs with Improved Query Time-Space Tradeoff
cites work: Faster approximate diameter and distance oracles in planar graphs
cites work: Exact Distance Oracles for Planar Graphs with Failing Vertices
cites work: Q5002738
cites work: Improved algorithms for min cut and max flow in undirected planar graphs
cites work: Multiple-source shortest paths in embedded graphs
cites work: Separator based sparsification. I: Planarity testing and minimum spanning trees
cites work: Fully-dynamic planarity testing in polylogarithmic time
cites work: Dynamic Plane Transitive Closure
cites work: Maintenance of a minimum spanning forest in a dynamic plane graph
cites work: Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time

Single-source shortest paths and strong connectivity in dynamic planar graphs (cites work)
cites work: An O ( n log n ) algorithm for maximum st -flow in a directed planar graph

Single-source shortest paths and strong connectivity in dynamic planar graphs (cites work)
cites work: A New Approach to Incremental Cycle Detection and Related Problems

Single-source shortest paths and strong connectivity in dynamic planar graphs (cites work)
cites work: Decremental strongly-connected components and single-source reachability in near-linear time

Single-source shortest paths and strong connectivity in dynamic planar graphs (cites work)
cites work: Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance

Single-source shortest paths and strong connectivity in dynamic planar graphs (cites work)
cites work: Decremental single-source reachability in planar digraphs

Single-source shortest paths and strong connectivity in dynamic planar graphs (cites work)
cites work: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity

Single-source shortest paths and strong connectivity in dynamic planar graphs (cites work)
cites work: Fully Dynamic Connectivity in O(log n(log log n)2) Amortized Expected Time

Single-source shortest paths and strong connectivity in dynamic planar graphs (cites work)
cites work: Faster Deterministic Fully-Dynamic Graph Connectivity

Single-source shortest paths and strong connectivity in dynamic planar graphs (cites work)
cites work: Dynamic graph connectivity in polylogarithmic worst case time

Single-source shortest paths and strong connectivity in dynamic planar graphs (cites work)
cites work: Structured recursive separator decompositions for planar graphs in linear time

Single-source shortest paths and strong connectivity in dynamic planar graphs (cites work)
cites work: Min st -Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time

Single-source shortest paths and strong connectivity in dynamic planar graphs (cites work)
cites work: Fast Algorithms for Shortest Paths in Planar Graphs, with Applications

Single-source shortest paths and strong connectivity in dynamic planar graphs (cites work)
cites work: Holiest minimum-cost paths and flows in surface graphs

Single-source shortest paths and strong connectivity in dynamic planar graphs (cites work)
cites work: Shortest paths in directed planar graphs with negative lengths

Single-source shortest paths and strong connectivity in dynamic planar graphs (cites work)
cites work: Shortest Paths in Planar Graphs with Real Lengths in O(nlog2 n/loglogn) Time

Single-source shortest paths and strong connectivity in dynamic planar graphs (DOI)
DOI: 10.1016/J.JCSS.2021.09.008