Sparsest cut on bounded treewidth graphs
From MaRDI portal
Publication:5495798
DOI10.1145/2488608.2488644zbMath1293.05042arXiv1305.1347OpenAlexW2115163112MaRDI QIDQ5495798
David Witmer, Anupam Gupta, Kunal Talwar
Publication date: 7 August 2014
Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1305.1347
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Linear programming (90C05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Graph designs and isomorphic decomposition (05C51)
Related Items (12)
Max-Cut Under Graph Constraints ⋮ Sparsest Cut in Planar Graphs, Maximum Concurrent Flows and Their Connections with the Max-Cut Problem ⋮ A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time ⋮ Mean isoperimetry with control on outliers: exact and approximation algorithms ⋮ Integrality gaps for colorful matchings ⋮ Unnamed Item ⋮ A Comprehensive Analysis of Polyhedral Lift-and-Project Methods ⋮ Approximating graph-constrained max-cut ⋮ Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problem ⋮ Strong reductions for extended formulations ⋮ Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs ⋮ A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints Using LP Hierarchies
This page was built for publication: Sparsest cut on bounded treewidth graphs
