SwePub - search: id:"swepub:oai:DiVA.org:mau-49...

Enumeration	Reference	Cover	Find
1.	Ashvinkumar, Vikrant, et al. (author) Local Routing in Sparse and Lightweight Geometric Graphs 2022 In: Algorithmica. - : Springer. - 0178-4617 .- 1432-0541. ; 84, s. 1316-1340 Journal article (peer-reviewed)abstract 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.

Ashvinkumar, Vikrant, et al. (author)
Local Routing in Sparse and Lightweight Geometric Graphs
2022
In: Algorithmica. - : Springer. - 0178-4617 .- 1432-0541. ; 84, s. 1316-1340
Journal article (peer-reviewed)abstract
- 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.

Träfflista för sökning "id:"swepub:oai:DiVA.org:mau-49961" "