Decremental single-source reachability in planar digraphs

DOI10.1145/3055399.3055480MaRDI QIDQ4978051zbMATH OpenOpenAlexFDO

Authors Giuseppe F. Italiano, Adam Karczmarz, Jakub Łącki, Piotr Sankowski

Publication date 17 August 2017

Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.11163

zbMATH Keywords

dynamic algorithmsplanar graphsreachability

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40)

Abstract: In this paper we show a new algorithm for the decremental single-source reachability problem in directed planar graphs. It processes any sequence of edge deletions in $O(nlo{g}^{2}nloglogn)$ total time and explicitly maintains the set of vertices reachable from a fixed source vertex. Hence, if all edges are eventually deleted, the amortized time of processing each edge deletion is only $O(lo{g}^{2}nloglogn)$, which improves upon a previously known $O(sqrtn)$ solution. We also show an algorithm for decremental maintenance of strongly connected components in directed planar graphs with the same total update time. These results constitute the first almost optimal (up to polylogarithmic factors) algorithms for both problems. To the best of our knowledge, these are the first dynamic algorithms with polylogarithmic update times on general directed planar graphs for non-trivial reachability-type problems, for which only polynomial bounds are known in general graphs.

Recommendations

• Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
• scientific article; zbMATH DE number 6850313
• Optimal decremental connectivity in planar graphs
• Optimal decremental connectivity in planar graphs
• Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs

Cited in

(17)

• Optimal decremental connectivity in planar graphs
• Single-source shortest paths and strong connectivity in dynamic planar graphs
• Improved deterministic algorithms for decremental reachability and strongly connected components
• Optimal decremental connectivity in planar graphs
• Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
• scientific article; zbMATH DE number 1104331 (Why is no real title available?)
• scientific article; zbMATH DE number 6850313 (Why is no real title available?)
• Dynamic effective resistances and approximate Schur complement on separable graphs
• Decremental SPQR-trees for Planar Graphs
• Decremental strongly connected components and single-source reachability in near-linear time
• Min-Cost Flow in Unit-Capacity Planar Graphs
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
• Distributed planar reachability in nearly optimal time
• Fully dynamic strongly connected components in planar digraphs
• Dynamic reachability in planar digraphs with one source and one sink
• Fine-grained complexity lower bounds for families of dynamic graphs
• Core-sparse Monge matrix multiplication: improved algorithm and applications

This page was built for publication: Decremental single-source reachability in planar digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4978051)