Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419422 | Discrete Applied Mathematics | 2012 | 7 Pages |
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
Charis Papadopoulos,