Colored Multiway Cuts in Generalized Tree Networks
Xin Xiao, LI Shu-guang · 2009
Given a graph with color dependent edge weights and a partial coloration on some distinguished vertices, the colored multiway cut problem is to extend the partial coloration such that all the vertices are colored and the total weight of edges that have different colored endpoints is minimized. A polynomial time algorithm is presented that solves the problem exactly for generalized tree networks.