A polynomial-time algorithm for the paired-domination problem on permutation graphs

摘要

A set S of vertices in a graph H = (V, E) with no isolated vertices is a paired-dominating set of H if every vertex of H is adjacent to at least one vertex in S and if the subgraph induced by S contains a perfect matching. Let G be a permutation graph and pi be its corresponding permutation. In this paper we present an O(mn) time algorithm for finding a minimum cardinality paired-dominating set for a permutation graph G with n vertices and m edges. (C) 2008 Elsevier B.V. All rights reserved.