Approximating Sparsest Cut in Graphs of Bounded Treewidth

DOI10.1007/978-3-642-15369-3_10zbMath1304.68213arXiv1006.3970OpenAlexW2071588464MaRDI QIDQ3588403

Robert Krauthgamer, Eden Chlamtáč, Prasad Raghavendra

Publication date: 10 September 2010

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1006.3970

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (7)

Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines ⋮ A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time ⋮ Integrality gaps for colorful matchings ⋮ Pathwidth, trees, and random embeddings ⋮ The complexity of finding uniform sparsest cuts in various graph classes ⋮ The Complexity Status of Problems Related to Sparsest Cuts ⋮ A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies

This page was built for publication: Approximating Sparsest Cut in Graphs of Bounded Treewidth