Minimum cost subpartitions in graphs

DOI10.1016/J.IPL.2006.11.011zbMATH Open1185.05139OpenAlexW2090987888MaRDI QIDQ845968FDOQ845968

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

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

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)

Cites Work

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

Cited In (11)

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

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)