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
Luleå tekniska universitet.
Show others and affiliations
2000 (English)In: Algorithms and Computation: 11th International Conference, ISAAC 2000 Taipei, Taiwan, December 18-20, 2000 Proceedings / [ed] D.T. Lee; Shang-Hua Teng, Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 2000, 47-59 p.Conference paper, Published paper (Refereed)
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
Berlin: Encyclopedia of Global Archaeology/Springer Verlag, 2000. 47-59 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 1969
National Category
Computer Sciences
Research subject
Dependable Communication and Computation Systems
Identifiers
URN: urn:nbn:se:ltu:diva-26846DOI: 10.1007/3-540-40996-3_5Local ID: 01abe9d0-f100-11dc-ba03-000ea68e967bISBN: 3-540-41255-7 (print)OAI: oai:DiVA.org:ltu-26846DiVA: diva2:1000026
Conference
International Symposium on Algorithms and Computation : 18/12/2000 - 20/12/2000
Note
Godkänd; 2000; 20080313 (ysko)Available from: 2016-09-30 Created: 2016-09-30 Last updated: 2017-11-25Bibliographically approved

Open Access in DiVA

fulltext(287 kB)14 downloads
File information
File name FULLTEXT01.pdfFile size 287 kBChecksum SHA-512
989dd085e17d90fa8aeea962fec5ec89280940c2c2e7ee8de923b3ddc1f2110d9147249e7d87b5fff7deb88c4a73636287aaf97d1e9415cd75f1fa1757160241
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Brodnik, Andrej
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 14 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
isbn
urn-nbn

Altmetric score

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