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

A set SS of vertices in a graph H=(V,E)H=(V,E) with no isolated vertices is a paired-dominating set   of HH if every vertex of HH is adjacent to at least one vertex in SS and if the subgraph induced by SS contains a perfect matching. Let GG be a permutation graph and ππ be its corresponding permutation. In this paper we present an O(mn)O(mn) time algorithm for finding a minimum cardinality paired-dominating set for a permutation graph GG with nn vertices and mm edges.