A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs

DOI10.1137/140981265zbMath1355.05201OpenAlexW2587032883MaRDI QIDQ2960472

Peng Li, Yaokun Wu

Publication date: 9 February 2017

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

Full work available at URL: https://semanticscholar.org/paper/07178a6b270caff731782af5d2ffc17f3e7d6163

zbMATH Keywords

Hamiltonian pathinterval representationforward degree sequence2-fixed-endpoint Hamiltonian path problemnormal vertex ordering

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (7)

A simple linear time algorithm to solve the MIST problem on interval graphs ⋮ Disjoint path covers joining prescribed source and sink sets in interval graphs ⋮ The longest cycle problem is polynomial on interval graphs ⋮ Polynomial time algorithm for \(k\)-vertex-edge dominating problem in interval graphs ⋮ A simple optimal algorithm for \(k\)-tuple dominating problem in interval graphs ⋮ Polynomial time algorithm for \(k\)-vertex-edge dominating problem in interval graphs ⋮ Parameterized complexity of \((A,\ell)\)-path packing

Cites Work

• Unnamed Item
• Unnamed Item
• An optimal algorithm for the \(k\)-fixed-endpoint path cover on proper interval graphs
• The longest path problem has a polynomial solution on interval graphs
• Linear algorithm for optimal path cover problem on interval graphs
• Finding Hamiltonian circuits in interval graphs
• Paths in interval graphs and circular arc graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The longest path problem is polynomial on cocomparability graphs
• The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
• A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs
• LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs
• The LBFS Structure and Recognition of Interval Graphs
• Linear Time LexDFS on Cocomparability Graphs.
• The 2-Terminal-Set Path Cover Problem and Its Polynomial Solution on Cographs
• A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs
• Maximal Neighborhood Search and Rigid Interval Graphs
• Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs

This page was built for publication: A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs