Compact oracles for reachability and approximate distances in planar digraphs
From MaRDI portal
Publication:5435672
DOI10.1145/1039488.1039493zbMath1125.68394OpenAlexW2096304547WikidataQ56533629 ScholiaQ56533629MaRDI QIDQ5435672
Publication date: 14 January 2008
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1039488.1039493
Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Search-space size in contraction hierarchies ⋮ Connectivity check in 3-connected planar graphs with obstacles ⋮ Routing among convex polygonal obstacles in the plane ⋮ Succinct posets ⋮ Metric Embedding via Shortest Path Decompositions ⋮ Covering metric spaces by few trees ⋮ Boolean dimension and tree-width ⋮ Routing in polygonal domains ⋮ Spanners for Directed Transmission Graphs ⋮ Metric decompositions of path-separable graphs ⋮ Strong-diameter decompositions of minor free graphs ⋮ Distance Labeling Schemes for $$K_4$$-Free Bridged Graphs ⋮ Labelings vs. embeddings: on distributed and prioritized representations of distances ⋮ Additive spanners and distance and routing labeling schemes for hyperbolic graphs ⋮ Implicit representation of relations ⋮ Brief Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes for Planar Graphs ⋮ Distributed computing of efficient routing schemes in generalized chordal graphs ⋮ General compact labeling schemes for dynamic trees ⋮ A parallel bio-inspired shortest path algorithm ⋮ Constant query time \((1 + \epsilon)\)-approximate distance oracle for planar graphs ⋮ Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ Labeling schemes for weighted dynamic trees ⋮ Routing in unit disk graphs ⋮ Efficient vertex-label distance oracles for planar graphs ⋮ Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs ⋮ Compact Routing in Unit Disk Graphs ⋮ Space-efficient path-reporting approximate distance oracles ⋮ Sparse covers for planar graphs and graphs that exclude a fixed minor ⋮ Faster approximate diameter and distance oracles in planar graphs ⋮ Join-reachability problems in directed graphs ⋮ Shortest-path queries in static networks ⋮ Constructing labeling schemes through universal matrices ⋮ Interval routing in reliability networks ⋮ Planar graphs, negative weight edges, shortest paths, and near linear time ⋮ On compact representations of all-pairs-shortest-path-distance matrices ⋮ Planar graphs, via well-orderly maps and trees ⋮ Efficient dynamic approximate distance oracles for vertex-labeled planar graphs ⋮ Improved Guarantees for Vertex Sparsification in Planar Graphs ⋮ Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs ⋮ Fault-tolerant distance labeling for planar graphs ⋮ Unnamed Item ⋮ A note on models for graph representations ⋮ Unnamed Item ⋮ Fast approximation of eccentricities and distances in hyperbolic graphs ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs ⋮ Labeling schemes for tree representation ⋮ Many distances in planar graphs ⋮ Covering Metric Spaces by Few Trees ⋮ Reachability oracles for directed transmission graphs ⋮ Localized and compact data-structure for comparability graphs ⋮ Distributed Computing of Efficient Routing Schemes in Generalized Chordal Graphs ⋮ A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs ⋮ Faster Approximate Diameter and Distance Oracles in Planar Graphs ⋮ On the Path Separability of Planar Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On vertex rankings of graphs and its relatives ⋮ Fault-tolerant distance labeling for planar graphs ⋮ Distance labeling schemes for \(K_4\)-free bridged graphs ⋮ Routing in Polygonal Domains
This page was built for publication: Compact oracles for reachability and approximate distances in planar digraphs
