License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2016.62
URN: urn:nbn:de:0030-drops-64033
URL: http://drops.dagstuhl.de/opus/volltexte/2016/6403/
Go to the corresponding LIPIcs Volume Portal


Li, Jian ; Zhan, Wei

Almost All Even Yao-Yao Graphs Are Spanners

pdf-format:
LIPIcs-ESA-2016-62.pdf (0.6 MB)


Abstract

It is an open problem whether Yao-Yao graphs YY_{k} (also known as sparse-Yao graphs) are all spanners when the integer parameter k is large enough. In this paper we show that, for any integer k >= 42, the Yao-Yao graph YY_{2k} is a t_k-spanner, with stretch factor t_k = 6.03+O(k^{-1}) when k tends to infinity. Our result generalizes the best known result which asserts that all YY_{6k} are spanners for k >= 6 [Bauer and Damian, SODA'13]. Our proof is also somewhat simpler.

BibTeX - Entry

@InProceedings{li_et_al:LIPIcs:2016:6403,
  author =	{Jian Li and Wei Zhan},
  title =	{{Almost All Even Yao-Yao Graphs Are Spanners}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{62:1--62:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Piotr Sankowski and Christos Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6403},
  URN =		{urn:nbn:de:0030-drops-64033},
  doi =		{10.4230/LIPIcs.ESA.2016.62},
  annote =	{Keywords: Yao-Yao graph, geometric spanner, curved trapezoid}
}

Keywords: Yao-Yao graph, geometric spanner, curved trapezoid
Seminar: 24th Annual European Symposium on Algorithms (ESA 2016)
Issue Date: 2016
Date of publication: 18.08.2016


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI