1 Search Results for "Shahaf, Gal"

Document
DOI: 10.4230/LIPIcs.ESA.2018.71
Large Low-Diameter Graphs are Good Expanders

Authors: Michael Dinitz, Michael Schapira, and Gal Shahaf

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
We revisit the classical question of the relationship between the diameter of a graph and its expansion properties. One direction is well understood: expander graphs exhibit essentially the lowest possible diameter. We focus on the reverse direction, showing that "sufficiently large" graphs of fixed diameter and degree must be "good" expanders. We prove this statement for various definitions of "sufficiently large" (multiplicative/additive factor from the largest possible size), for different forms of expansion (edge, vertex, and spectral expansion), and for both directed and undirected graphs. A recurring theme is that the lower the diameter of the graph and (more importantly) the larger its size, the better the expansion guarantees. Aside from inherent theoretical interest, our motivation stems from the domain of network design. Both low-diameter networks and expanders are prominent approaches to designing high-performance networks in parallel computing, HPC, datacenter networking, and beyond. Our results establish that these two approaches are, in fact, inextricably intertwined. We leave the reader with many intriguing questions for future research.
Cite as

Michael Dinitz, Michael Schapira, and Gal Shahaf. Large Low-Diameter Graphs are Good Expanders. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 71:1-71:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dinitz_et_al:LIPIcs.ESA.2018.71,
  author =	{Dinitz, Michael and Schapira, Michael and Shahaf, Gal},
  title =	{{Large Low-Diameter Graphs are Good Expanders}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{71:1--71:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.71},
  URN =		{urn:nbn:de:0030-drops-95348},
  doi =		{10.4230/LIPIcs.ESA.2018.71},
  annote =	{Keywords: Network design, Expander graphs, Spectral graph theory}
}
  • Refine by Author
  • 1 Dinitz, Michael
  • 1 Schapira, Michael
  • 1 Shahaf, Gal

  • Refine by Classification
  • 1 Mathematics of computing → Extremal graph theory
  • 1 Mathematics of computing → Spectra of graphs
  • 1 Networks → Network design principles
  • 1 Networks → Network structure

  • Refine by Keyword
  • 1 Expander graphs
  • 1 Network design
  • 1 Spectral graph theory

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact