Finding minimum dominating cycles in permutation graphs |
| |
| Authors: | Charles J Colbourn J.Mark Keil Lorna K Stewart |
| |
| Affiliation: | Department of Computer Science, University of Waterloo, Waterloo, Ont. N2L 3G1, Canada;Department of Computational Science, University of Saskatchewan, Saskatoon, Sask. S7N OW0, Canada;Department of Computer Science, University of Toronto, Toronto, Ont. M5S IA I, Canada |
| |
| Abstract: | A dominating cycle for a graph G = (V, E) is a subset C of V which has the following properties: (i) the subgraph of G induced by C has a Hamiltonian cycle, and (ii) every vertex of V is adjacent to some vertex of C. In this paper, we develop an O(n2) algorithm for finding a minimum cardinality dominating cycle in a permutation graph. We also show that a minimum cardinality dominating cycle in a permutation graph always has an even number of vertices unless it is isomorphic to C3. |
| |
| Keywords: | dominating set dominating cycle permutation graph polynomial algorithm |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
