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