Search: id:"swepub:oai:lup.lub.lu.se:7b2840ab-fcad-4643-9206-12687648ef68" >
Approximate distanc...
Approximate distance oracles revisited
- Article/chapterEnglish2002
Publisher, publication year, extent ...
Numbers
-
LIBRIS-ID:oai:lup.lub.lu.se:7b2840ab-fcad-4643-9206-12687648ef68
-
https://lup.lub.lu.se/record/311041URI
Supplementary language notes
-
Language:English
-
Summary in:English
Part of subdatabase
Classification
-
Subject category:kon swepub-publicationtype
-
Subject category:ref swepub-contenttype
Notes
-
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.
Subject headings and genre
Added entries (persons, corporate bodies, meetings, titles ...)
-
Levcopoulos, ChristosLund University,Lunds universitet,Data Vetenskap,Naturvetenskapliga fakulteten,Computer Science,Faculty of Science(Swepub:lu)cs-cle
(author)
-
Narasimhan, G
(author)
-
Smid, M
(author)
-
Data VetenskapNaturvetenskapliga fakulteten
(creator_code:org_t)
Related titles
-
In:Algorithms and Computation, Proceedings / Lecture Notes in Computer Science2518, s. 357-3680302-97431611-3349
Internet link
Find in a library
To the university's database