Minimum cost subpartitions in graphs

DOI10.1016/J.IPL.2006.11.011MaRDI QIDQ845968zbMATH OpenOpenAlexFDO

Authors Hiroshi Nagamochi, Yoko Kamidoi

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

graphclusteringpartitionapproximation algorithmscut\(k\)-way cutextreme vertex sets

Mathematics Subject Classification ID

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

Recommendations

• Approximation the minimum \(k\)-way cut in a graph via minimum 3-way cuts
• scientific article; zbMATH DE number 3891429
• scientific article; zbMATH DE number 1522944
• An Improved Divide-and-Conquer Algorithm for Finding All Minimum k-Way Cuts
• On minimum 3-cuts and approximating k-cuts using cut trees

Cites work

• scientific article; zbMATH DE number 2119718 (Why is no real title available?)
• A Deterministic Algorithm for Finding All Minimum k‐Way Cuts
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• A new approach to the minimum cut problem
• Approximation the minimum \(k\)-way cut in a graph via minimum 3-way cuts
• Connectivity and edge-disjoint spanning trees
• Edge-connectivity augmentation problems
• Finding k Cuts within Twice the Optimal
• GRAPH ALGORITHMS FOR NETWORK CONNECTIVITY PROBLEMS(<Special Issue>Network Design, Control and Optimization)
• On minimum 3-cuts and approximating k-cuts using cut trees
• Optimal attack and reinforcement of a network
• Tree packing and approximating \(k\)-cuts

Cited in

(11)

• Fast and Deterministic Approximations for k-Cut.
• Approximating submodular \(k\)-partition via principal partition sequence
• On the complexity of isoperimetric problems on trees
• Minimum Cost Partitions of Trees with Supply and Demand
• A linear-time algorithm for finding an edge-partition with max-min ratio at most two
• LP relaxation and tree packing for minimum \(k\)-cut
• Minimum degree orderings
• Fast and deterministic approximations for \(k\)-cut
• Minimizing branching vertices in distance-preserving subgraphs
• Faster algorithms for all-pairs bounded min-cuts
• Min-Max Graph Partitioning and Small Set Expansion

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q845968)