Meny

Du är här

Approximate distance oracles for geometric graphs

Författare:
Publiceringsår: 2002
Språk: Engelska
Sidor: 828-837
Publikation/Tidskrift/Serie: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms
Dokumenttyp: Konferensbidrag
Förlag: Society for Industrial and Applied Mathematics

Sammanfattning

Given a geometric t-spanner graph G in Ed with n points and m edges, with edge lengths that lie within a polynomial (in n) factor of each other. Then, after O(m+n log n) preprocessing, we present an approximation scheme to answer (1+ε)-approximate shortest path queries in O(1) time. The data structure uses O(n log n) space.

Disputation

Nyckelord

  • Technology and Engineering

Övriga

13th Annual ACM/SIAM Symposium on Discrete Algorithms
2014-01-07
San Francisco, California, United States
Published
Yes
  • ISBN: 0-89871-513-X

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