The small set vertex expansion problem

DOI10.1016/J.TCS.2021.07.017MaRDI QIDQ2232595zbMATH OpenOpenAlexFDO

Authors Garima Agrawal, Soumen Maity

Publication date 6 October 2021

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2021.07.017

zbMATH Keywords

treewidthparameterized complexityFPTclique widthneighbourhood diversityW[1-hard]

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• The small set vertex expansion problem
• Minimizing the union: tight approximations for small set bipartite vertex expansion
• Approximation algorithms for hypergraph small set expansion and small set vertex expansion
• On Set Expansion Problems and the Small Set Expansion Conjecture
• Approximation algorithms for hypergraph small-set expansion and small-set vertex expansion

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• A threshold of ln n for approximating set cover
• Algorithmic meta-theorems for restrictions of treewidth
• Approximation algorithms for hypergraph small-set expansion and small-set vertex expansion
• Expander flows, geometric embeddings and graph partitioning
• Graph Layout Problems Parameterized by Vertex Cover
• Graph expansion and the unique games conjecture
• Graph minors. III. Planar tree-width
• Integer Programming with a Fixed Number of Variables
• Minimizing the union: tight approximations for small set bipartite vertex expansion
• Minkowski's Convex Body Theorem and Integer Programming
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• New tools for graph coloring
• Parameterized algorithms
• Recent developments on graphs of bounded clique-width
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• The densest \(k\)-subhypergraph problem
• Treewidth. Computations and approximations

Cited in

(3)

• On the parameterized complexity of \textsc{Sparsest Cut} and \textsc{Small-Set Expansion} problems
• On Set Expansion Problems and the Small Set Expansion Conjecture
• The small set vertex expansion problem

This page was built for publication: The small set vertex expansion problem

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