Malmö University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Local Routing in Sparse and Lightweight Geometric Graphs
Univ Sydney, Sydney, NSW, Australia..
Univ Sydney, Sydney, NSW, Australia..
Lund Univ, Lund, Sweden..
Malmö University, Faculty of Technology and Society (TS), Department of Computer Science and Media Technology (DVMT).ORCID iD: 0000-0002-1342-8618
Show others and affiliations
2022 (English)In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 84, p. 1316-1340Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Springer, 2022. Vol. 84, p. 1316-1340
Keywords [en]
Computational geometry, Spanners, Routing
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:mau:diva-49961DOI: 10.1007/s00453-022-00930-2ISI: 000746779100001Scopus ID: 2-s2.0-85123504940OAI: oai:DiVA.org:mau-49961DiVA, id: diva2:1635479
Available from: 2022-02-07 Created: 2022-02-07 Last updated: 2024-02-05Bibliographically approved

Open Access in DiVA

fulltext(725 kB)295 downloads
File information
File name FULLTEXT01.pdfFile size 725 kBChecksum SHA-512
c9525042d93e662beb4d5f2de689ad822fee1ce41eca38570dce3c120cd22d29ba40246a7d99d5a776e972d7a6649f9d994328005d38c09e9d5be57e39cb4c07
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopus

Authority records

Nilsson, Bengt J.

Search in DiVA

By author/editor
Nilsson, Bengt J.
By organisation
Department of Computer Science and Media Technology (DVMT)
In the same journal
Algorithmica
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 295 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 375 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf