Planar Reachability Under Single Vertex or Edge Failures - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2021

Planar Reachability Under Single Vertex or Edge Failures

Résumé

In this paper we present an efficient reachability oracle under single-edge or single-vertex failures for planar directed graphs. Specifically, we show that a planar digraph G can be preprocessed in O(n log 2 n/log log n) time, producing an O(n log n)-space data structure that can answer in O(log n) time whether u can reach v in G if the vertex x (the edge f) is removed from G, for any query vertices u, v and failed vertex x (failed edge f). To the best of our knowledge, this is the first data structure for planar directed graphs with nearly optimal preprocessing time that answers all-pairs queries under any kind of failures in polylogarithmic time. We also consider 2-reachability problems, where we are given a planar digraph G and we wish to determine if there are two vertex-disjoint (edge-disjoint) paths from u to v, for query vertices u, v. In this setting we provide a nearly optimal 2-reachability oracle, which is the existential variant of the reachability oracle under single failures, with the following bounds. We can construct in O(n polylog n) time an O(n log 3+o(1) n)-space data structure that can check in O(log 2+o(1) n) time for any query vertices u, v whether v is 2-reachable from u, or otherwise find some separating vertex (edge) x lying on all paths from u to v in G. To obtain our results, we follow the general recursive approach of Thorup for reachability in planar graphs [J. ACM '04] and we present new data structures which generalize dominator trees and previous data structures for strong-connectivity under failures [Georgiadis et al., SODA '17]. Our new data structures work also for general digraphs and may be of independent interest.
Fichier principal
Vignette du fichier
2101.02574.pdf (585.59 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03474039 , version 1 (10-12-2021)

Identifiants

Citer

Giuseppe F Italiano, Adam Karczmarz, Nikos Parotsidis. Planar Reachability Under Single Vertex or Edge Failures. SODA 2021 - ACM-SIAM Symposium on Discrete Algorithms, Jan 2021, Alexandria, United States. pp.2739-2758, ⟨10.1137/1.9781611976465.163⟩. ⟨hal-03474039⟩

Collections

INRIA INRIA2
9 Consultations
114 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More