Publikationer från Malmö universitet
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • 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ö universitet, Fakulteten för teknik och samhälle (TS), Institutionen för datavetenskap och medieteknik (DVMT).ORCID-id: 0000-0002-1342-8618
Vise andre og tillknytning
2022 (engelsk)Inngår i: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 84, s. 1316-1340Artikkel i tidsskrift (Fagfellevurdert) 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.

sted, utgiver, år, opplag, sider
Springer, 2022. Vol. 84, s. 1316-1340
Emneord [en]
Computational geometry, Spanners, Routing
HSV kategori
Identifikatorer
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
Tilgjengelig fra: 2022-02-07 Laget: 2022-02-07 Sist oppdatert: 2024-02-05bibliografisk kontrollert

Open Access i DiVA

fulltext(725 kB)301 nedlastinger
Filinformasjon
Fil FULLTEXT01.pdfFilstørrelse 725 kBChecksum SHA-512
c9525042d93e662beb4d5f2de689ad822fee1ce41eca38570dce3c120cd22d29ba40246a7d99d5a776e972d7a6649f9d994328005d38c09e9d5be57e39cb4c07
Type fulltextMimetype application/pdf

Andre lenker

Forlagets fulltekstScopus

Person

Nilsson, Bengt J.

Søk i DiVA

Av forfatter/redaktør
Nilsson, Bengt J.
Av organisasjonen
I samme tidsskrift
Algorithmica

Søk utenfor DiVA

GoogleGoogle Scholar
Totalt: 301 nedlastinger
Antall nedlastinger er summen av alle nedlastinger av alle fulltekster. Det kan for eksempel være tidligere versjoner som er ikke lenger tilgjengelige

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 393 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf