π/2-Angle yao graphs are spanners

Download
  1. (PDF, 513 KB)
  2. Get@NRC: π/2-Angle yao graphs are spanners (Opens in a new window)
DOIResolve DOI: http://doi.org/10.1007/978-3-642-17514-5
AuthorSearch for: ; Search for: ; Search for: ; Search for: ; Search for: ; Search for: ; Search for:
TypeBook Chapter
Proceedings titleAlgorithms and Computation : 21st International Symposium, ISAAC 2010, Jeju, Korea, December 15-17, 2010, Proceedings, Part II
Series titleLecture Notes In Computer Science; Volume 6507
ConferenceThe 21st International Symposium on Algorithms and Computation (ISAAC 2010), December 15-17, 2010, Jeju Island, Korea
ISSN0302-9743
ISBN978-3-642-17513-8
978-3-642-17514-5
Pages446457; # of pages: 12
AbstractWe show that the Yao graph Y₄ in the L₂ metric is a spanner with stretch factor 8 √2(29 + 23 √2).
Publication date
PublisherSpringer Berlin Heidelberg
LanguageEnglish
AffiliationNational Research Council Canada (NRC-CNRC); NRC Institute for Information Technology
Peer reviewedYes
NPARC number16350494
Export citationExport as RIS
Report a correctionReport a correction
Record identifierb5712542-720e-4226-8919-42c3d65ea51e
Record created2010-11-10
Record modified2016-07-19
Bookmark and share
  • Share this page with Facebook (Opens in a new window)
  • Share this page with Twitter (Opens in a new window)
  • Share this page with Google+ (Opens in a new window)
  • Share this page with Delicious (Opens in a new window)