Paths in interval graphs and circular arc graphs
type: Item
instance of: scholarly article
title: Paths in interval graphs and circular arc graphs
zbMATH Open document ID: 0777.05081
DOI: 10.1016/0012-365X(93)90223-G
author: Peter Damaschke
published in: Discrete Mathematics
publication date: 1993-08-30T00:00:00Z
review text: Interval graphs and circular arc graphs are intersection graphs of intervals on a line resp. of arcs on a circle. We give polynomial-time algorithms for several path cover problems in such graphs, e.g. for finding a Hamiltonian path in a circular arc graph. Some seemingly similar problems remain open here: Can one find in polynomial time (1) a Hamiltonian cycle in a circular arc graph, (2) a Hamiltonian path with prescribed start vertex in an interval graph?
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 179588
zbMATH Keywords: circular arc graphs
zbMATH Keywords: intersection graphs
zbMATH Keywords: polynomial-time algorithms
zbMATH Keywords: Hamiltonian path
MaRDI profile type: Publication
cites work: Finding maximum cliques on circular-arc graphs
cites work: Finding Hamiltonian circuits in proper interval graphs
cites work: Hamiltonian circuits in interval graph generalizations
cites work: Achromatic number is NP-complete for cographs and interval graphs
cites work: Dominating sets and domatic number of circular arc graphs
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: The Hamiltonian circuit problem for circle graphs is NP-complete
cites work: Domination in convex and chordal bipartite graphs
cites work: Q4198056
cites work: A Characterization of Comparability Graphs and of Interval Graphs
cites work: Q3328583
cites work: Interval graphs and related topics
cites work: The NP-completeness column: an ongoing guide
cites work: Finding Hamiltonian circuits in interval graphs
cites work: An optimal algorithm for finding dominating cycles in circular-arc graphs
Recommended article: Interval bigraphs and circular arc graphs
Recommended article: Paths, cycles, and arc‐connectivity in digraphs
Recommended article: Pathwidth of Circular-Arc Graphs
Recommended article: Proper circular arc graphs as intersection graphs of paths on a grid
Recommended article: Graphs and digraphs represented by intervals and circular arcs
Recommended article: Longest Paths in Circular Arc Graphs
Recommended article: Paths and circuits in g-graphs
Recommended article: A note on longest paths in circular arc graphs
Recommended article: Paths in graphs
description: scientific article; zbMATH DE number 179588