Publikationer från Malmö universitet
Driftstörningar
Det förekommer återkommande driftstörningar på några av sök-portalerna på grund av hög belastning. Vi arbetar på att lösa problemet, ni kan tillfälligt mötas av ett felmeddelande.
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat 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
Visa övriga samt affilieringar
2022 (Engelska)Ingår i: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 84, s. 1316-1340Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
Springer, 2022. Vol. 84, s. 1316-1340
Nyckelord [en]
Computational geometry, Spanners, Routing
Nationell ämneskategori
Datavetenskap (datalogi)
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
Tillgänglig från: 2022-02-07 Skapad: 2022-02-07 Senast uppdaterad: 2024-02-05Bibliografiskt granskad

Open Access i DiVA

fulltext(725 kB)301 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 725 kBChecksumma SHA-512
c9525042d93e662beb4d5f2de689ad822fee1ce41eca38570dce3c120cd22d29ba40246a7d99d5a776e972d7a6649f9d994328005d38c09e9d5be57e39cb4c07
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltextScopus

Person

Nilsson, Bengt J.

Sök vidare i DiVA

Av författaren/redaktören
Nilsson, Bengt J.
Av organisationen
Institutionen för datavetenskap och medieteknik (DVMT)
I samma tidskrift
Algorithmica
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 301 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 394 träffar
RefereraExporteraLänk till posten
Permanent länk

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