Approximate distance oracles
From MaRDI portal
Publication:5175966
DOI10.1145/380752.380798zbMath1323.05126OpenAlexW2093455937WikidataQ60299166 ScholiaQ60299166MaRDI QIDQ5175966
Publication date: 27 February 2015
Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.94.333
Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Approximation algorithms (68W25)
Related Items
Average case analysis for tree labelling schemes ⋮ Limitations to Fréchet's metric embedding method ⋮ Spanners for bounded tree-length graphs ⋮ Covering metric spaces by few trees ⋮ Approximate distance oracles for graphs with dense clusters ⋮ Energy-efficient paths in radio networks ⋮ Cycle bases in graphs characterization, algorithms, complexity, and applications ⋮ Compact and localized distributed data structures ⋮ Compact roundtrip routing with topology-independent node names ⋮ Online computation with advice ⋮ Approximate shortest paths guided by a small index ⋮ On compact representations of all-pairs-shortest-path-distance matrices ⋮ Efficient dynamic approximate distance oracles for vertex-labeled planar graphs ⋮ Graph spanners: a tutorial review ⋮ On compact and efficient routing in certain graph classes ⋮ Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs ⋮ The Greedy Spanner Is Existentially Optimal ⋮ Multiplicative Approximations of Random Walk Transition Probabilities ⋮ Covering Metric Spaces by Few Trees ⋮ Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths ⋮ Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC ⋮ Unnamed Item ⋮ Distance Labeling for Permutation Graphs
Cites Work
