Search: id:"swepub:oai:DiVA.org:mau-12690" >
Local Routing in Sp...
Local Routing in Sparse and Lightweight Geometric Graphs
-
- Ashvinkumar, Vikrant (author)
- University of Sydney, Australia
-
- Gudmundsson, Joachim (author)
- University of Sydney, Australia
-
- Levcopoulos, Christos (author)
- Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH
-
show more...
-
- Nilsson, Bengt J. (author)
- Malmö University,Malmö universitet,Institutionen för datavetenskap och medieteknik (DVMT)
-
- van Renssen, André (author)
- University of Sydney, Australia
-
show less...
-
(creator_code:org_t)
- Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2019
- 2019
- English.
-
In: LIPICS. - : Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. ; 149, s. 1-30
- Related links:
-
https://doi.org/10.4...
-
show more...
-
http://itcs.shufe.ed...
-
https://mau.diva-por... (primary) (Raw object)
-
http://www.dagstuhl.... (free)
-
http://drops.dagstuh... (free)
-
http://dx.doi.org/10... (free)
-
https://urn.kb.se/re...
-
https://doi.org/10.4...
-
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 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
- Computational geometry
- Spanners
- Routing
Publication and Content Type
- ref (subject category)
- kon (subject category)
Find in a library
-
LIPICS
(Search for host publication in LIBRIS)
To the university's database