Approximate distance oracles for graphs with dense clusters

M. Andersson, C. Levcopoulos, J. Gudmundsson

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)


Let TeX be a collection of N pairwise vertex disjoint TeX -spanners where the weight of an edge is equal to the Euclidean distance between its endpoints. Let TeX be a graph on TeX with M edges of non-negative weight. The union of the two graphs is denoted TeX . We present a data structure of size TeX that answers (1+e)-approximate shortest path queries in TeX in constant time, where e>¿0 is constant.
Original languageEnglish
Title of host publicationAlgorithms and Computation (Proceedings 15th International Symposium, ISAAC 2004, Hong Kong, December 20-22, 2004)
EditorsR. Fleischer, G. Trippen
Place of PublicationBerlin
ISBN (Print)3-540-24131-0
Publication statusPublished - 2004

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'Approximate distance oracles for graphs with dense clusters'. Together they form a unique fingerprint.

Cite this