Finding minimum dominating cycles in permutation graphs
type: Item
instance of: scholarly article
title: Finding minimum dominating cycles in permutation graphs
zbMATH Open document ID: 0569.90091
DOI: 10.1016/0167-6377(85)90044-6
author: Charles J. Colbourn
author: J. Mark Keil
author: Lorna Stewart
published in: Operations Research Letters
publication date: 1985-01-01T00:00:00Z
review text: 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(n^ 2)\) 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 \(C_ 3\).
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 3910165
zbMATH Keywords: dominating set
zbMATH Keywords: polynomial algorithm
zbMATH Keywords: dominating cycle
zbMATH Keywords: subgraph
zbMATH Keywords: Hamiltonian cycle
zbMATH Keywords: permutation graph
MaRDI profile type: Publication
full work available at URL: 0167-6377(85)90044-6
OpenAlex ID: W1986855028
cites work: Towards a theory of domination in graphs
cites work: Permutation graphs: Connected domination and Steiner trees
cites work: Q3684150
cites work: Clustering and domination in perfect graphs
cites work: Domination in permutation graphs
cites work: On Eulerian and Hamiltonian Graphs and Line Graphs
cites work: On Spanning and Dominating Circuits in Graphs
cites work: Minimum dominating cycles in 2-trees
cites work: Minimum dominating cycles in outerplanar graphs
cites work: Existence of dominating cycles and paths
Recommended article: Finding a minimum independent dominating set in a permutation graph
Recommended article: Q4218434
Recommended article: An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs
Recommended article: Minimum 2-tuple dominating set of permutation graphs
Recommended article: An $O(N + M)$-Time Algorithm for Finding a Minimum-Weight Dominating Set in a Permutation Graph
Recommended article: An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs
Recommended article: Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs
Recommended article: Domination in permutation graphs
Recommended article: On cycle permutation graphs
Recommended article: On the Enumeration and Counting of Minimal Dominating sets in Interval and Permutation Graphs
description: scientific article; zbMATH DE number 3910165