A new and improved algorithm for the 3-cut problem

DOI10.1016/S0167-6377(97)00043-6zbMath0908.90263MaRDI QIDQ1267194

Olivier Goldschmidt, Michel Burlet

Publication date: 18 March 1999

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

zbMATH Keywords

edge-weighted graphmin cutminimum 3-cut

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (10)

On generalized greedy splitting algorithms for multiway partition problems ⋮ Efficient algorithms for the problems of enumerating cuts by non-decreasing weights ⋮ An exact model for cell formation in group technology ⋮ Clique Cover and Graph Separation ⋮ Efficient Algorithms for the k Smallest Cuts Enumeration ⋮ Tight approximation ratio of a general greedy splitting algorithm for the minimum \(k\)-way cut problem ⋮ Generating partitions of a graph into a fixed number of minimum weight cuts ⋮ Greedy splitting algorithms for approximating multiway partition problems ⋮ Finding minimum 3-way cuts in hypergraphs ⋮ Computation and algorithm for the minimum \(k\)-edge-connectivity of graphs

Cites Work

• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• Unnamed Item
• Unnamed Item

This page was built for publication: A new and improved algorithm for the 3-cut problem