Isolation branching: a branch and bound algorithm for the \(k \)-terminal cut problem

DOI10.1007/s10878-020-00534-yzbMath1502.90157OpenAlexW4245681592MaRDI QIDQ2082183

Dorit S. Hochbaum, Mark Velednitsky

Publication date: 4 October 2022

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-020-00534-y

zbMATH Keywords

optimizationclusteringbranch-and-bound\(k\)-terminal cutminimum isolating cut

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Uses Software

• NetworkX
• Gurobi
• Python

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Solving \((k-1)\)-stable instances of \(k\)-Terminal Cut with isolating cuts
• An improved parameterized algorithm for the minimum node multiway cut problem
• Rounding algorithms for a geometric embedding of minimum multiway cut
• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• The Complexity of Multiterminal Cuts
• Multiway cut, pairwise realizable distributions, and descending thresholds
• Parameterized and Exact Computation
• Simplex partitioning via exponential clocks and the multiway cut problem

This page was built for publication: Isolation branching: a branch and bound algorithm for the \(k \)-terminal cut problem