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 (m n) time algorithm for finding a minimum cardinality paired-dominating set for a permutation graph G with n vertices and m edges.
- Permutation graph
ASJC Scopus subject areas
- Applied Mathematics
- Discrete Mathematics and Combinatorics