The complexity status of problems related to sparsest cuts
DOI10.1007/978-3-642-19222-7_14zbMATH Open1326.68145OpenAlexW1675722546MaRDI QIDQ3000501FDOQ3000501
Authors: Paul Bonsma, Viresh Patel, Hajo Broersma, Artem Pyatkin 
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
Recommendations
- The complexity of finding uniform sparsest cuts in various graph classes
- Sparsest cuts and bottlenecks in graphs
- Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem
- Sparsest cut on bounded treewidth graphs: algorithms and hardness results
- On the hardness of approximating Multicut and Sparsest-Cut
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)
Cites Work
- NP-hardness of Euclidean sum-of-squares clustering
- Title not available (Why is that?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Title not available (Why is that?)
- Some simplified NP-complete graph problems
- Title not available (Why is that?)
- Clustering large graphs via the singular value decomposition
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Expander flows, geometric embeddings and graph partitioning
- Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut
- Approximating sparsest cut in graphs of bounded treewidth
- Sparsest cuts and concurrent flows in product graphs.
- \(O(\sqrt{\log n})\) approximation to sparsest cut in \(\tilde{O}(n^2)\) time
- Linear time algorithms for finding sparsest cuts in various graph classes
- Sparsest cuts and bottlenecks in graphs
- Evaluating a branch-and-bound RLT-based algorithm for minimum sum-of-squares clustering
- Title not available (Why is that?)
Cited In (6)
- A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP
- Linear time algorithms for finding sparsest cuts in various graph classes
- The Complexity of Partial Function Extension for Coverage Functions
- The complexity of finding uniform sparsest cuts in various graph classes
- Increasing the minimum degree of a graph by contractions
- On the hardness of approximating Multicut and Sparsest-Cut
This page was built for publication: The complexity status of problems related to sparsest cuts
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3000501)
