The Power of Dynamic Distance Oracles

DOI10.1145/2746539.2746615zbMath1321.68389arXiv1308.3336OpenAlexW2093101813MaRDI QIDQ2941483

Anna Zych, Jakub Oćwieja, Jakub Łącki, Piotr Sankowski, Marcin Pilipczuk

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

approximationSteiner treedynamic algorithmdynamic distance oracles

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Approximation algorithms (68W25) Signed and weighted graphs (05C22)

Related Items (14)

Approximate distance oracles with improved stretch for sparse graphs ⋮ The nearest colored node in a tree ⋮ Unnamed Item ⋮ Succinct data structures for nearest colored node in a tree ⋮ A theory and algorithms for combinatorial reoptimization ⋮ Unnamed Item ⋮ A Local-Search Algorithm for Steiner Forest ⋮ Symmetry exploitation for online machine covering with bounded migration ⋮ Decremental SPQR-trees for Planar Graphs ⋮ Efficient vertex-label distance oracles for planar graphs ⋮ Efficient dynamic approximate distance oracles for vertex-labeled planar graphs ⋮ Approximate distance oracles with improved stretch for sparse graphs ⋮ Robust online algorithms for dynamic choosing problems ⋮ Inferring local transition functions of discrete dynamical systems from observations of system behavior

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming

This page was built for publication: The Power of Dynamic Distance Oracles