Paths in interval graphs and circular arc graphs

DOI10.1016/0012-365X(93)90223-GzbMath0777.05081MaRDI QIDQ1210553

Peter Damaschke

Publication date: 30 August 1993

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

zbMATH Keywords

Hamiltonian path; intersection graphs; polynomial-time algorithms; circular arc graphs

Mathematics Subject Classification ID

05C38: Paths and cycles

05C85: Graph algorithms (graph-theoretic aspects)

05C45: Eulerian and Hamiltonian graphs

Related Items

Path partition for graphs with special blocks, Solving the path cover problem on circular-arc graphs by using an approximation algorithm

Cites Work

• Domination in convex and chordal bipartite graphs
• Finding Hamiltonian circuits in proper interval graphs
• Interval graphs and related topics
• Finding Hamiltonian circuits in interval graphs
• Dominating sets and domatic number of circular arc graphs
• Hamiltonian circuits in interval graph generalizations
• Finding maximum cliques on circular-arc graphs
• An optimal algorithm for finding dominating cycles in circular-arc graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The Hamiltonian circuit problem for circle graphs is NP-complete
• Achromatic number is NP-complete for cographs and interval graphs
• The NP-completeness column: an ongoing guide
• A Characterization of Comparability Graphs and of Interval Graphs
• Unnamed Item
• Unnamed Item