Advertisement
Published in:
01-01-2014
On the generalized multiway cut in trees problem
Published in: Journal of Combinatorial Optimization | Issue 1/2014
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
Given a tree \(T = (V, E)\) with \(n\) vertices and a collection of terminal sets \(D = \{S_1, S_2, \ldots , S_c\}\), where each \(S_i\) is a subset of \(V\) and \(c\) is a constant, the generalized multiway cut in trees problem (GMWC(T)) asks to find a minimum size edge subset \(E^{\prime } \subseteq E\) such that its removal from the tree separates all terminals in \(S_i\) from each other for each terminal set \(S_i\). The GMWC(T) problem is a natural generalization of the classical multiway cut in trees problem, and has an implicit relation to the Densest \(k\)-Subgraph problem. In this paper, we show that the GMWC(T) problem is fixed-parameter tractable by giving an \(O(n^2 + 2^k)\) time algorithm, where \(k\) is the size of an optimal solution, and the GMWC(T) problem is polynomial time solvable when the problem is restricted in paths.We also discuss some heuristics for the GMWC(T) problem