Sökning: onr:"swepub:oai:DiVA.org:mau-12690" >
Local Routing in Sp...
Local Routing in Sparse and Lightweight Geometric Graphs
-
- Ashvinkumar, Vikrant (författare)
- University of Sydney, Australia
-
- Gudmundsson, Joachim (författare)
- University of Sydney, Australia
-
- Levcopoulos, Christos (författare)
- 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
-
visa fler...
-
- Nilsson, Bengt J. (författare)
- Malmö University,Malmö universitet,Institutionen för datavetenskap och medieteknik (DVMT)
-
- van Renssen, André (författare)
- University of Sydney, Australia
-
visa färre...
-
(creator_code:org_t)
- Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2019
- 2019
- Engelska.
-
Ingår i: LIPICS. - : Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. ; 149, s. 1-30
- Relaterad länk:
-
https://doi.org/10.4...
-
visa fler...
-
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...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- Computational geometry
- Spanners
- Routing
- Computational geometry
- Spanners
- Routing
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
-
LIPICS
(Sök värdpublikationen i LIBRIS)
Till lärosätets databas