On cutting a few vertices from a graph

DOI10.1016/S0166-218X(02)00394-3zbMath1019.68137MaRDI QIDQ1811082

Kobbi Nissim, Robert Krauthgamer, Uriel Feige

Publication date: 10 June 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

dynamic programminggraph partitioningapproximation algorithmsrandom edge contraction

Mathematics Subject Classification ID

Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (7)

Approximation algorithms for the weighted \(t\)-uniform sparsest cut and some other graph partitioning problems ⋮ Parameterized complexity of immunization in the threshold model ⋮ Immunization in the threshold model: a parameterized complexity study ⋮ A new approximation algorithm for the unbalanced min \(s\)-\(t\) cut problem ⋮ Heuristics for the data arrangement problem on regular trees ⋮ Unbalanced graph cuts with minimum capacity ⋮ Multi-parameter analysis for local graph partitioning problems: using greediness for parameterization

Cites Work

• Finding good approximate vertex and edge partitions is NP-hard
• Some simplified NP-complete graph problems
• Approximating the minimum bisection size (extended abstract)
• A new approach to the minimum cut problem
• A Polylogarithmic Approximation of the Minimum Bisection
• Unnamed Item

This page was built for publication: On cutting a few vertices from a graph