Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs

DOI10.1007/978-3-642-22006-7_12zbMath1332.68033arXiv1104.5214OpenAlexW3101337733MaRDI QIDQ3012798

Ken-ichi Kawarabayashi, Christian Sommer, Philip N. Klein

Publication date: 6 July 2011

Published in: Automata, Languages and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Related Items

Efficient vertex-label distance oracles for planar graphs ⋮ Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs ⋮ Shortest-Path Queries in Geometric Networks ⋮ Space-efficient path-reporting approximate distance oracles ⋮ Faster approximate diameter and distance oracles in planar graphs ⋮ Shortest-path queries in static networks ⋮ Efficient dynamic approximate distance oracles for vertex-labeled planar graphs ⋮ Local algorithms for sparse spanning graphs ⋮ Faster Approximate Diameter and Distance Oracles in Planar Graphs ⋮ Unnamed Item ⋮ Short and Simple Cycle Separators in Planar Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved algorithms for dynamic shortest paths
• A data structure for dynamic trees
• Distance estimation and object location via rings of neighbors
• Planar graphs, negative weight edges, shortest paths, and near linear time
• Maintaining information in fully dynamic trees with top trees
• Oracles for bounded-length shortest paths in planar graphs
• Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs
• Undirected single-source shortest paths with positive integer weights in linear time
• Shortest path queries in planar graphs
• Fast and Compact Oracles for Approximate Distances in Planar Graphs
• Approximate distance oracles
• Bypassing the embedding
• Shortest Paths in Planar Graphs with Real Lengths in O(nlog2 n/loglogn) Time
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• A Separator Theorem for Planar Graphs
• A Data Structure for Dynamically Maintaining Rooted Trees
• Floats, Integers, and Single Source Shortest Paths
• Distance Oracles for Sparse Graphs
• Object location using path separators
• Compact oracles for reachability and approximate distances in planar digraphs
• Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
• Many distances in planar graphs
• Faster shortest-path algorithms for planar graphs

This page was built for publication: Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs