On Set Expansion Problems and the Small Set Expansion Conjecture

DOI10.1007/978-3-319-12340-0_16MaRDI QIDQ2945189zbMATH OpenOpenAlexFDO

Authors Rajiv Gandhi, Guy Kortsarz

Publication date 9 September 2015

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-12340-0_16

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• On set expansion problems and the small set expansion conjecture
• The small set vertex expansion problem
• The small set vertex expansion problem
• scientific article; zbMATH DE number 940705
• Small-set expansion in shortcode graph and the 2-to-2 conjecture
• Some remarks on small sets
• scientific article; zbMATH DE number 5145372
• Counting sets with small sumset and applications
• On Sets with a Small Subset Sum
• On small sets of integers

Cited in

(6)

• The small set vertex expansion problem
• Inapproximability of maximum biclique problems, minimum k-cut and densest at-least- k-subgraph from the small set expansion hypothesis
• The small set vertex expansion problem
• On set expansion problems and the small set expansion conjecture
• Small Generating Sets and DLPC Problem
• Inapproximability of maximum edge biclique, maximum balanced biclique and minimum k-cut from the small set expansion hypothesis

This page was built for publication: On Set Expansion Problems and the Small Set Expansion Conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2945189)