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
Online routing in convex subdivisions
School of Computer Science, Carleton University, Ottawa.
University of Karlskona/Ronneby.
Massachusetts Institute of Technology, Laboratory for Computer Science, Cambridge.
Show others and affiliations
2002 (English)In: International journal of computational geometry and applications, ISSN 0218-1959, Vol. 12, no 4, p. 283-295Article in journal (Refereed) Published
Abstract [en]

We consider online routing algorithms for finding paths between the vertices of plane graphs. We show (1) there exists a routing algorithm for arbitrary triangulations that has no memory and uses no randomization, (2) no equivalent result is possible for convex subdivisions, (3) there is no competitive online routing algorithm under the Euclidean distance metric in arbitrary triangulations, and (4) there is no competitive online routing algorithm under the link distance metric even when the input graph is restricted to be a Delaunay, greedy, or minimum-weight triangulation

Place, publisher, year, edition, pages
2002. Vol. 12, no 4, p. 283-295
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
URN: urn:nbn:se:ltu:diva-12613DOI: 10.1142/S021819590200089XISI: 000177708900003Scopus ID: 2-s2.0-0036695524Local ID: bc4d0410-bf01-11de-b769-000ea68e967bOAI: oai:DiVA.org:ltu-12613DiVA, id: diva2:985564
Note
Validerad; 2002; 20091022 (andbra)Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2018-07-10Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Brodnik, Andrej

Search in DiVA

By author/editor
Brodnik, Andrej
In the same journal
International journal of computational geometry and applications
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 29 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