The complexity of finding uniform sparsest cuts in various graph classes

DOI10.1016/J.JDA.2011.12.008MaRDI QIDQ450559zbMATH OpenOpenAlexFDO

Authors Paul Bonsma, Viresh Patel, Hajo Broersma, Artem Pyatkin

Publication date 13 September 2012

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2011.12.008

zbMATH Keywords

clique-widthparameterized complexitysparsest cuttreewidthunit interval graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (05C99) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• The complexity status of problems related to sparsest cuts
• Linear time algorithms for finding sparsest cuts in various graph classes
• Sparsest cut on bounded treewidth graphs: algorithms and hardness results
• Sparsest cuts and bottlenecks in graphs
• scientific article; zbMATH DE number 1496855

Cites work

• \(O(\sqrt{\log n})\) approximation to sparsest cut in \(\tilde{O}(n^2)\) time
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• Algorithmic lower bounds for problems parameterized by clique-width
• Approximating clique-width and branch-width
• Approximating sparsest cut in graphs of bounded treewidth
• Clustering large graphs via the singular value decomposition
• Depth-First Search and Linear Graph Algorithms
• Expander flows, geometric embeddings and graph partitioning
• scientific article; zbMATH DE number 1688377 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• scientific article; zbMATH DE number 1512682 (Why is no real title available?)
• scientific article; zbMATH DE number 1361465 (Why is no real title available?)
• Linear time algorithms for finding sparsest cuts in various graph classes
• Linear time solvable optimization problems on graphs of bounded clique-width
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• NP-hardness of Euclidean sum-of-squares clustering
• On the clique-width of some perfect graph classes
• Parametrized complexity theory.
• Sparsest cuts and bottlenecks in graphs
• Sparsest cuts and concurrent flows in product graphs.
• The complexity status of problems related to sparsest cuts
• Upper bounds to the clique width of graphs

Cited in

(12)

• Sparsest cuts and concurrent flows in product graphs.
• A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time
• The complexity status of problems related to sparsest cuts
• Linear time algorithms for finding sparsest cuts in various graph classes
• Sparsest cut on bounded treewidth graphs: algorithms and hardness results
• A study on modularity density maximization: column generation acceleration and computational complexity analysis
• Solving cut-problems in quadratic time for graphs with bounded treewidth
• Combinatorial Fiedler theory and graph partition
• On the parameterized complexity of \textsc{Sparsest Cut} and \textsc{Small-Set Expansion} problems
• A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} time
• Graph algorithm based submodular function for sparsest cut problem
• Approximating sparsest cut in low-treewidth graphs via combinatorial diameter

This page was built for publication: The complexity of finding uniform sparsest cuts in various graph classes

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