Decomposing a graph into expanding subgraphs

DOI10.1002/rsa.20727zbMath1378.05170arXiv1502.00409MaRDI QIDQ4601444

Asaf Shapira, Guy Moshkovitz

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

hypercube; graph decomposition; small set expansion; graph expansion

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

05C51: Graph designs and isomorphic decomposition