Finding minimum dominating cycles in permutation graphs

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

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

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 cyclepolynomial algorithmdominating setsubgraphpermutation graphdominating cycle

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Extremal problems in graph theory (05C35)

Related Items (9)

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

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

This page was built for publication: Finding minimum dominating cycles in permutation graphs