An optimal algorithm for finding dominating cycles in circular-arc graphs

DOI10.1016/0166-218X(92)90201-KzbMath0753.05063OpenAlexW2060722839MaRDI QIDQ1186160

J. Mark Keil, Doug Schaefer

Publication date: 28 June 1992

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(92)90201-k

zbMATH Keywords

Hamiltonian cycleoptimal algorithmcircular-arc graphsdominating cycles

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs ⋮ Improved algorithms and complexity results for power domination in graphs ⋮ Paths in interval graphs and circular arc graphs ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Domination, independent domination, and duality in strongly chordal graphs
• On a circle-cover minimization problem
• Finding minimum dominating cycles in permutation graphs
• Dominating sets and domatic number of circular arc graphs
• Clustering and domination in perfect graphs
• Domination in permutation graphs
• A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
• Minimum dominating cycles in 2-trees
• Minimum dominating cycles in outerplanar graphs
• Dominating Sets in Chordal Graphs

This page was built for publication: An optimal algorithm for finding dominating cycles in circular-arc graphs