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

Abstract

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 π 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.