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 pathintersection graphspolynomial-time algorithmscircular arc graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Related Items

Cyclability in graph classes ⋮ The Longest Path Problem Is Polynomial on Interval Graphs ⋮ A simple linear time algorithm to solve the MIST problem on interval graphs ⋮ Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs ⋮ Disjoint path covers joining prescribed source and sink sets in interval graphs ⋮ The longest path problem is polynomial on cocomparability graphs ⋮ The 2-Terminal-Set Path Cover Problem and Its Polynomial Solution on Cographs ⋮ An optimal algorithm for the \(k\)-fixed-endpoint path cover on proper interval graphs ⋮ A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs ⋮ The longest path problem has a polynomial solution on interval graphs ⋮ Hamiltonian paths in some classes of grid graphs ⋮ The 1-fixed-endpoint path cover problem is Polynomial on interval graphs ⋮ Computing and counting longest paths on circular-arc graphs in polynomial time ⋮ The longest cycle problem is polynomial on interval graphs ⋮ Path partition for graphs with special blocks ⋮ A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs ⋮ An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs ⋮ The Longest Path Problem is Polynomial on Cocomparability Graphs ⋮ ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES ⋮ On the Power of Graph Searching for Cocomparability Graphs ⋮ Kernelization of Graph Hamiltonicity: Proper $H$-Graphs ⋮ Computing and Counting Longest Paths on Circular-Arc Graphs in Polynomial Time ⋮ Solving the path cover problem on circular-arc graphs by using an approximation algorithm ⋮ Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs ⋮ Parameterized complexity of \((A,\ell)\)-path packing

Cites Work

• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Paths in interval graphs and circular arc graphs