Decomposing a graph into expanding subgraphs

DOI10.1137/1.9781611973730.85zbMath1378.05170arXiv1502.00409OpenAlexW2746518621MaRDI QIDQ4601444

Guy Moshkovitz, Asaf Shapira

Publication date: 16 January 2018

Published in: Random Structures & Algorithms, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1502.00409

zbMATH Keywords

hypercubegraph decompositionsmall set expansiongraph expansion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph designs and isomorphic decomposition (05C51)

Related Items (2)

Finding and Using Expanders in Locally Sparse Graphs ⋮ Towards the Erdős-Gallai cycle decomposition conjecture

This page was built for publication: Decomposing a graph into expanding subgraphs