SwePub
Sök i LIBRIS databas

  Extended search

WFRF:(Demaine Erik D.)
 

Search: WFRF:(Demaine Erik D.) > Online routing in c...

  • Bose, ProsenjitSchool of Computer Science, Carleton University, Ottawa, Canada (author)

Online routing in convex subdivisions

  • Article/chapterEnglish2000

Publisher, publication year, extent ...

  • 2002-01-29
  • Berlin :Encyclopedia of Global Archaeology/Springer Verlag,2000
  • electronicrdacarrier

Numbers

  • LIBRIS-ID:oai:DiVA.org:ltu-26846
  • https://urn.kb.se/resolve?urn=urn:nbn:se:ltu:diva-26846URI
  • https://doi.org/10.1007/3-540-40996-3_5DOI

Supplementary language notes

  • Language:English
  • Summary in:English

Part of subdatabase

Classification

  • Subject category:ref swepub-contenttype
  • Subject category:kon swepub-publicationtype

Notes

  • Godkänd; 2000; 20080313 (ysko)
  • 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.

Subject headings and genre

Added entries (persons, corporate bodies, meetings, titles ...)

  • Brodnik, AndrejLuleå tekniska universitet,IMFM, University of Ljubljana, Ljubljana, Slovenia(Swepub:ltu)brodnik (author)
  • Carlsson, SvanteUniversity of Karlskrona/Ronneby, Karlskrona, Sweden (author)
  • Demaine, Erik D.Department of Computer Science, University of Waterloo, Waterloo, Canada (author)
  • Fleischer, RudolfDepartment of Computer Science, University of Waterloo, Waterloo, Canada (author)
  • López-Ortiz, AlejandroFaculty of Computer Science, University of New Brunswick, Fredericton, Canada (author)
  • Morin, PatSchool of Computer Science, Carleton University, Ottawa, Canada (author)
  • Munro, J. IanDepartment of Computer Science, University of Waterloo, Waterloo, Canada (author)
  • Luleå tekniska universitetSchool of Computer Science, Carleton University, Ottawa, Canada (creator_code:org_t)

Related titles

  • In:Algorithms and ComputationBerlin : Encyclopedia of Global Archaeology/Springer Verlag, s. 47-593540412557

Internet link

Find in a library

To the university's database

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

 
pil uppåt Close

Copy and save the link in order to return to this view