scientific article; zbMATH DE number 176254

From MaRDI portal
Publication:4035360





Let \(G= (V, E)\) be an undirected graph with vertex set \(V\), edge set \(E\) and a set of specified terminal nodes \(A= \{t_ 1, t_ 2,\dots, t_ k\}\subseteq V\). A \(k\)-terminal cut is a set \(C\subseteq E\) such that no two terminals of \(A\) are in the same components of \(G- C\). The optimal \(k\)-terminal cut problem is: given \(G\) and a cost vector \(c\in {\mathbf R}^ E_ +\), find a \(k\)-terminal cut of minimum cost. For \(k= 2\), this problem can be solved efficiently using maximal flow. However, for \(k\geq 3\) the problem is NP-complete. The author presents a number of complexity results as well as a method for constructing feasible solutions using 2-terminal cuts. Lower bounds, based on linear programming cutting plane are presented. A number of results on the structure of the polyhedron determined by the \(k\)-terminal cuts of a graph are established. For the entire collection see [Zbl 0753.00028].




Cited in
(47)








This page was built for publication:

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