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

DOI10.1007/S10878-020-00534-YMaRDI QIDQ2082183zbMATH OpenOpenAlexFDO

Authors Mark Velednitsky, Dorit S. Hochbaum

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

\(k\)-terminal cutbranch-and-boundclusteringminimum isolating cutoptimization

Mathematics Subject Classification ID

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

Recommendations

• Isolation branching: a branch and bound algorithm for the k-terminal cut problem
• Computational study of a branching algorithm for the maximum \(k\)-cut problem
• A branch-and-bound algorithm for solving max-\(k\)-cut problem
• Solving \((k-1)\)-stable instances of \(k\)-Terminal Cut with isolating cuts
• Solving \((k-1)\)-stable instances of \texttt{k-terminal cut} with isolating cuts
• A branch-and-cut algorithm for the k-edge connected subgraph problem
• The multi-terminal vertex separator problem: branch-and-cut-and-price
• The multi-terminal vertex separator problem: polyhedral analysis and branch-and-cut
• Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem
• Multi-multiway cut problem on graphs of bounded branch width

Cites work

• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• A Polynomial Algorithm for the k-cut Problem for Fixed k
• An improved parameterized algorithm for the minimum node multiway cut problem
• Approximation algorithms for NP-hard problems.
• scientific article; zbMATH DE number 4204092 (Why is no real title available?)
• scientific article; zbMATH DE number 5485510 (Why is no real title available?)
• scientific article; zbMATH DE number 1775387 (Why is no real title available?)
• Multiway cut, pairwise realizable distributions, and descending thresholds
• Parameterized and Exact Computation
• Simplex partitioning via exponential clocks and the multiway cut problem
• Solving \((k-1)\)-stable instances of \(k\)-Terminal Cut with isolating cuts
• The Complexity of Multiterminal Cuts

Cited in

(5)

• Pruning by isomorphism in branch-and-cut
• Solving \((k-1)\)-stable instances of \texttt{k-terminal cut} with isolating cuts
• Solving \((k-1)\)-stable instances of \(k\)-Terminal Cut with isolating cuts
• Isolation branching: a branch and bound algorithm for the k-terminal cut problem
• scientific article; zbMATH DE number 1757963 (Why is no real title available?)

Describes a project that uses

Uses Software

• Gurobi
• NetworkX
• Python

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2082183)