1 Search Results for "Kwok, Tsz Chiu"


Document
Lower Bounds on Expansions of Graph Powers

Authors: Tsz Chiu Kwok and Lap Chi Lau

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)


Abstract
Given a lazy regular graph G, we prove that the expansion of G^t is at least sqrt(t) times the expansion of G. This bound is tight and can be generalized to small set expansion. We show some applications of this result.

Cite as

Tsz Chiu Kwok and Lap Chi Lau. Lower Bounds on Expansions of Graph Powers. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 313-324, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{kwok_et_al:LIPIcs.APPROX-RANDOM.2014.313,
  author =	{Kwok, Tsz Chiu and Lau, Lap Chi},
  title =	{{Lower Bounds on Expansions of Graph Powers}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{313--324},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.313},
  URN =		{urn:nbn:de:0030-drops-47057},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.313},
  annote =	{Keywords: Conductance, Expansion, Graph power, Random walk}
}
  • Refine by Author
  • 1 Kwok, Tsz Chiu
  • 1 Lau, Lap Chi

  • Refine by Classification

  • Refine by Keyword
  • 1 Conductance
  • 1 Expansion
  • 1 Graph power
  • 1 Random walk

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2014

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail