Sökning: id:"swepub:oai:lup.lub.lu.se:001bc5c1-af26-4ec1-a682-10492797ae62" >
Fast greedy algorit...
Fast greedy algorithms for constructing sparse geometric spanners
-
Gudmundsson, J (författare)
-
- Levcopoulos, Christos (författare)
- Lund University,Lunds universitet,Data Vetenskap,Naturvetenskapliga fakulteten,Computer Science,Faculty of Science
-
Narasimhan, G (författare)
-
(creator_code:org_t)
- 2002
- 2002
- Engelska.
-
Ingår i: SIAM Journal on Computing. - 0097-5397. ; 31:5, s. 1479-1500
- Relaterad länk:
-
http://dx.doi.org/10...
-
visa fler...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- Given a set V of n points in R-d and a real constant t > 1, we present the first O(n log n)-time algorithm to compute a geometric t-spanner on V. A geometric t-spanner on V is a connected graph G = ( V, E) with edge weights equal to the Euclidean distances between the endpoints, and with the property that, for all u, v is an element of V the distance between u and v in G is at most t times the Euclidean distance between u and v. The spanner output by the algorithm has O(n) edges and weight O(1).wt (MST), and its degree is bounded by a constant.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- sparse geometric spanners
- cluster graph
- computational geometry
Publikations- och innehållstyp
- art (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas