On minimum 3-cuts and approximating k-cuts using Cut Trees

DOI10.1007/3-540-61310-2_11zbMath1415.90104OpenAlexW1571566323MaRDI QIDQ4645919

Sanjiv Kapoor

Publication date: 11 January 2019

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-61310-2_11

zbMATH Keywords

minimum weightmaximum flow problemgraph partitioning problembounding techniquepartition tree

Mathematics Subject Classification ID

Integer programming (90C10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (7)

A lower bound of \(8/(7+\frac{1}{k-1})\) on the integrality ratio of the Călinescu-Karloff-Rabani relaxation for multiway cut ⋮ On generalized greedy splitting algorithms for multiway partition problems ⋮ Minimum cost subpartitions in graphs ⋮ Efficient Algorithms for the k Smallest Cuts Enumeration ⋮ Generating partitions of a graph into a fixed number of minimum weight cuts ⋮ On the \(k\)-cut problem ⋮ Finding minimum 3-way cuts in hypergraphs

Cites Work

• Tough graphs and Hamiltonian circuits.
• An improved algorithm for the planar 3-cut problem
• An $O ( | V |^2 )$ Algorithm for the Planar 3-Cut Problem
• Optimal attack and reinforcement of a network
• Multi-Terminal Network Flows
• On the multiway cut polyhedron
• Multiprocessor Scheduling with the Aid of Network Flow Algorithms
• A simple min-cut algorithm

This page was built for publication: On minimum 3-cuts and approximating k-cuts using Cut Trees