Full Paper: Search Google Scholar

Given a directed graph G, a set of k terminals and an integer p, the Directed Vertex Multiway Cut problem asks if there is a set S of at most p (nonterminal) vertices whose removal disconnects each terminal from all other terminals. Directed Edge Multiway Cut is the analogous problem where S is a set of at most p edges. These two problems indeed are known to be equivalent. A natural generalization of the multiway cut is the multicut problem, in which we want to disconnect only a set of k given pairs instead of all pairs. Marx (Theor. Comp. Sci.

 

 

 

Discussion

Post anonymously: (You can change the anonymity of a comment at any time.)

You must be logged in to comment. Log in

No comments yet.