Meny

Javascript verkar inte påslaget? - Vissa delar av Lunds universitets webbplats fungerar inte optimalt utan javascript, kontrollera din webbläsares inställningar.
Du är här

Approximate distance oracles revisited

Författare:
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

Övriga

13th International Symposium, ISAAC 2002
2014-11-22
Vancouver, BC, Canada
Published
Yes
  • ISSN: 0302-9743

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen