Publikationer
Approximate distance oracles revisited
Avdelning/ar:
Publiceringsår: 2002
Språk: Engelska
Sidor: 357-368
Publikation/Tidskrift/Serie: Algorithms and Computation, Proceedings / Lecture Notes in Computer Science
Volym: 2518
Dokumenttyp: Konferensbidrag
Förlag: SPRINGER-VERLAG BERLIN
Sammanfattning
Let G be a geometric t-spanner in E-d with n vertices and m edges, where t is a constant. We show that G can be preprocessed in O(m log n) time, such that (1 + epsilon)-approximate shortest-path queries in G can be answered in O(1) time. The data structure uses O(n log n) space.
Disputation
Nyckelord
- Technology and Engineering
Övrigt
13th International Symposium, ISAAC 2002
2013-11-22
Vancouver, BC, Canada
Published
Yes
- ISSN: 0302-9743
