Search: id:"swepub:oai:DiVA.org:mau-49961" >
Local Routing in Sp...
Local Routing in Sparse and Lightweight Geometric Graphs
-
- Ashvinkumar, Vikrant (author)
- Univ Sydney, Sydney, NSW, Australia.,University of Sydney
-
- Gudmundsson, Joachim (author)
- Univ Sydney, Sydney, NSW, Australia.,University of Sydney
-
- Levcopoulos, Christos (author)
- Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Naturvetenskapliga fakulteten,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH,Faculty of Science
-
show more...
-
- Nilsson, Bengt J. (author)
- Malmö University,Malmö universitet,Institutionen för datavetenskap och medieteknik (DVMT)
-
- van Renssen, Andre (author)
- Univ Sydney, Sydney, NSW, Australia.,University of Sydney
-
show less...
-
Univ Sydney, Sydney, NSW, Australia University of Sydney (creator_code:org_t)
- 2022-01-25
- 2022
- English.
-
In: Algorithmica. - : Springer. - 0178-4617 .- 1432-0541. ; 84, s. 1316-1340
- Related links:
-
https://doi.org/10.1...
-
show more...
-
https://mau.diva-por... (primary) (Raw object)
-
https://link.springe...
-
http://dx.doi.org/10... (free)
-
https://urn.kb.se/re...
-
https://doi.org/10.1...
-
https://lup.lub.lu.s...
-
show less...
Abstract
Subject headings
Close
- Online routing in a planar embedded graph is central to a number of fields and has been studied extensively in the literature. For most planar graphs no O (1)-competitive online routing algorithm exists. A notable exception is the Delaunay triangulation for which Bose and Morin (SIAM J Comput 33(4):937-951, 2004) showed that there exists an online routing algorithm that is O(1)-competitive. However, a Delaunay triangulation can have Omega (n) vertex degree and a total weight that is a linear factor greater than the weight of a minimum spanning tree. We show a simple construction, given a set V of n points in the Euclidean plane, of a planar geometric graph on V that has small weight (within a constant factor of the weight of a minimum spanning tree on V), constant degree, and that admits a local routing strategy that is O (1)-competitive. Moreover, the technique used to bound the weight works generally for any planar geometric graph whilst preserving the admission of an O (1)-competitive routing strategy.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- Computational geometry
- Spanners
- Routing
Publication and Content Type
- ref (subject category)
- art (subject category)
Find in a library
To the university's database