Sökning: onr:"swepub:oai:lup.lub.lu.se:13bf10d3-b9a9-497d-bc1d-fb2f4dcc9de5" >
Approximate distanc...
Approximate distance oracles for graphs with dense clusters
-
- Andersson, Mattias (författare)
- Lund University,Lunds universitet,Data Vetenskap,Naturvetenskapliga fakulteten,Computer Science,Faculty of Science
-
Gudmundsson, Joachim (författare)
-
- Levcopoulos, Christos (författare)
- Lund University,Lunds universitet,Data Vetenskap,Naturvetenskapliga fakulteten,Computer Science,Faculty of Science
-
(creator_code:org_t)
- Elsevier BV, 2007
- 2007
- Engelska.
-
Ingår i: Computational Geometry. - : Elsevier BV. - 0925-7721. ; 37:3, s. 142-154
- Relaterad länk:
-
http://dx.doi.org/10...
-
visa fler...
-
https://doi.org/10.1...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publikations- och innehållstyp
- art (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas