| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 420716 | Discrete Applied Mathematics | 2009 | 10 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
T.C.E. Cheng, Liying Kang, Erfang Shan,