Approximation algorithms for the weighted \(t\)-uniform sparsest cut and some other graph partitioning problems
From MaRDI portal
Publication:295639
DOI10.1016/j.jcss.2016.03.004zbMath1342.68358MaRDI QIDQ295639
Mohammad Khairul Hasan, Kyung-Yong Chwa
Publication date: 13 June 2016
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2016.03.004
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- On cutting a few vertices from a graph
- Cut problems in graphs with a budget constraint
- Approximations for the isoperimetric and spectral profile of graphs and related parameters
- Unbalanced Graph Partitioning
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
- Euclidean distortion and the sparsest cut
- An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
- Approximate max-flow min-(multi)cut theorems and their applications
- Min-max Graph Partitioning and Small Set Expansion
- Expander flows, geometric embeddings and graph partitioning
- A tight bound on approximating arbitrary metrics by tree metrics