Finding minimum dominating cycles in permutation graphs

DOI10.1016/0167-6377(85)90044-6zbMath0569.90091MaRDI QIDQ1060966

Charles J. Colbourn, J. Mark Keil, Lorna K. Stewart

Publication date: 1985

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(85)90044-6

zbMATH Keywords

Hamiltonian cycle; polynomial algorithm; dominating set; subgraph; permutation graph; dominating cycle

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

05C35: Extremal problems in graph theory

Related Items

Computing residual connectedness reliability for restricted networks, Bibliography on domination in graphs and some basic definitions of domination parameters, Finding a maximum independent set in a permutation graph, Bipartite permutation graphs, On domination problems for permutation and other graphs, Dominating sets in perfect graphs, Dominating cycles in Halin graphs, An optimal algorithm for finding dominating cycles in circular-arc graphs

Cites Work

• Unnamed Item
• Clustering and domination in perfect graphs
• Existence of dominating cycles and paths
• Permutation graphs: Connected domination and Steiner trees
• Domination in permutation graphs
• Minimum dominating cycles in 2-trees
• Minimum dominating cycles in outerplanar graphs
• On Spanning and Dominating Circuits in Graphs
• Towards a theory of domination in graphs
• On Eulerian and Hamiltonian Graphs and Line Graphs