Decremental single-source reachability in planar digraphs

DOI10.1145/3055399.3055480zbMATH Open1370.05200arXiv1705.11163OpenAlexW2618849866MaRDI QIDQ4978051FDOQ4978051

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

Publication date: 17 August 2017

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

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.

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

zbMATH Keywords

reachabilityplanar graphsdynamic algorithms

Mathematics Subject Classification ID

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

Cited In (8)

• Min-Cost Flow in Unit-Capacity Planar Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
• Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time
• Decremental SPQR-trees for Planar Graphs
• Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
• Single-source shortest paths and strong connectivity in dynamic planar graphs

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)