The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Approximate distance oracles for graphs with dense clusters

På svenska

Author

Summary, in English

Let H1=(V,E1) be a collection of N pairwise vertex disjoint O(1)-spanners where the weight of an edge is equal to the Euclidean distance between its endpoints. Let H2=(V,E2) be the graph on V with M edges of non-negative weight. The union of the two graphs is denoted G=(V,E1 u E2). We present a data structure of size O(M^2 + nlogn) that answers (1+ε)-approximate shortest path queries in G in constant time, where ε>0 is constant.

Department/s

  • Computer Science

Publishing year

2007

Language

English

Pages

142-154

Publication/Series

Computational Geometry

Volume

37

Issue

3

Document type

Journal article

Publisher

Elsevier

Topic

  • Computer Science

Status

Published

Project

  • VR 2005-4085

ISBN/ISSN/Other

  • ISSN: 0925-7721