On the \(k\)-cut problem

DOI10.1016/S0167-6377(99)00071-1zbMath0955.90142OpenAlexW2079730767MaRDI QIDQ1977642

Francisco Barahona

Publication date: 17 May 2000

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0167-6377(99)00071-1

zbMATH Keywords

clusteringminimum cutsubmodular functions\(k\)-cut problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items

The vertex \(k\)-cut problem, On integer and bilevel formulations for the \(k\)-vertex cut problem, Bidirected and unidirected capacity installation in telecommunication networks., LP Relaxation and Tree Packing for Minimum $k$-Cut, Fast and Deterministic Approximations for k-Cut., Approximating \(k\)-cuts using network strength as a Lagrangean relaxation, Dynamic evolution of economically preferred facilities, Unnamed Item, Algorithms for the non-bifurcated network design problem

Cites Work

• Unnamed Item
• Unnamed Item
• Separating from the dominant of the spanning tree polytope
• Geometric algorithms and combinatorial optimization
• A faster algorithm for computing the strength of a network
• Tough graphs and Hamiltonian circuits.
• Optimal attack and reinforcement of a network
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• An $\NC$ Algorithm for Minimum Cuts
• A new approach to the minimum cut problem
• On minimum 3-cuts and approximating k-cuts using Cut Trees
• Network Design Using Cut Inequalities
• Approximation Algorithms for Min-k-Overlap Problems Using the Principal Lattice of Partitions Approach