The Complexity Status of Problems Related to Sparsest Cuts
From MaRDI portal
Publication:3000501
DOI10.1007/978-3-642-19222-7_14zbMath1326.68145OpenAlexW1675722546MaRDI QIDQ3000501
Paul Bonsma, Viresh Patel, Artem V. Pyatkin, Hajo J. Broersma
Publication date: 19 May 2011
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-19222-7_14
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Increasing the minimum degree of a graph by contractions ⋮ The complexity of finding uniform sparsest cuts in various graph classes ⋮ The Complexity of Partial Function Extension for Coverage Functions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Evaluating a branch-and-bound RLT-based algorithm for minimum sum-of-squares clustering
- Clustering large graphs via the singular value decomposition
- Sparsest cuts and bottlenecks in graphs
- NP-hardness of Euclidean sum-of-squares clustering
- Some simplified NP-complete graph problems
- Sparsest cuts and concurrent flows in product graphs.
- Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
- $O(\sqrt{\logn})$ Approximation to SPARSEST CUT in $\tilde{O}(n^2)$ Time
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Linear time algorithms for finding sparsest cuts in various graph classes
- Approximating Sparsest Cut in Graphs of Bounded Treewidth
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Expander flows, geometric embeddings and graph partitioning
