Article ID Journal Published Year Pages File Type
419422 Discrete Applied Mathematics 2012 7 Pages PDF
Abstract

Given an undirected graph and pairs of terminals the Restricted Vertex Multicut problem asks for a minimum set of nonterminal vertices whose removal disconnects each pair of terminals. The problem is known to be NP-complete for trees and polynomial-time solvable for interval graphs. In this paper we give a polynomial-time algorithm for the problem on permutation graphs. Furthermore we show that the problem remains NP-complete on split graphs whereas it becomes polynomial-time solvable for the class of co-bipartite graphs.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,