Decremental single-source reachability in planar digraphs

DOI10.1145/3055399.3055480zbMath1370.05200arXiv1705.11163OpenAlexW2618849866MaRDI QIDQ4978051

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)

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

zbMATH Keywords

reachabilityplanar graphsdynamic algorithms

Mathematics Subject Classification ID

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

Related Items (6)

Unnamed Item ⋮ Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ Decremental SPQR-trees for Planar Graphs ⋮ Min-Cost Flow in Unit-Capacity Planar Graphs ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs ⋮ Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time

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