On set expansion problems and the small set expansion conjecture

DOI10.1016/J.DAM.2015.05.028zbMath1319.05105OpenAlexW620970122WikidataQ123002417 ScholiaQ123002417MaRDI QIDQ494429

Rajiv Gandhi, Guy Kortsarz

Publication date: 1 September 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2015.05.028

zbMATH Keywords

edge coveringdense graphssmall set expansion

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Density (toughness, etc.) (05C42)

Related Items (1)

Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications

Cites Work

• Unnamed Item
• Unnamed Item
• \(k\)-edge subgraph problems
• On the \(k\)-edge-incident subgraph problem and its variants
• Detecting high log-densities
• Graph expansion and the unique games conjecture
• On Set Expansion Problems and the Small Set Expansion Conjecture
• Density Functions subject to a Co-Matroid Constraint.
• Primal-Dual Schema for Capacitated Covering Problems
• Finding Dense Subgraphs with Size Bounds
• On Finding Dense Subgraphs
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• The dense \(k\)-subgraph problem

This page was built for publication: On set expansion problems and the small set expansion conjecture