Minimum cost subpartitions in graphs

DOI10.1016/j.ipl.2006.11.011zbMath1185.05139OpenAlexW2090987888MaRDI QIDQ845968

Yoko Kamidoi, Hiroshi Nagamochi

Publication date: 29 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.11.011

zbMATH Keywords

partitiongraphclusteringcutapproximation algorithms\(k\)-way cutextreme vertex sets

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40)

Related Items (6)

Minimum degree orderings ⋮ LP Relaxation and Tree Packing for Minimum $k$-Cut ⋮ Fast and Deterministic Approximations for k-Cut. ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the complexity of isoperimetric problems on trees

Cites Work

• Unnamed Item
• Unnamed Item
• Edge-connectivity augmentation problems
• Connectivity and edge-disjoint spanning trees
• Optimal attack and reinforcement of a network
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• Finding k Cuts within Twice the Optimal
• A new approach to the minimum cut problem
• On minimum 3-cuts and approximating k-cuts using Cut Trees
• GRAPH ALGORITHMS FOR NETWORK CONNECTIVITY PROBLEMS(<Special Issue>Network Design, Control and Optimization)
• A Deterministic Algorithm for Finding All Minimum k‐Way Cuts
• Approximation the minimum \(k\)-way cut in a graph via minimum 3-way cuts

This page was built for publication: Minimum cost subpartitions in graphs