A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs

DOI10.1016/j.tcs.2009.11.003zbMath1222.05117OpenAlexW2060774395MaRDI QIDQ2268855

Stavros D. Nikolopoulos, Katerina Asdre

Publication date: 9 March 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.11.003

zbMATH Keywords

perfect graphslinear-time algorithmsproper interval graphspath coverfixed-endpoint path cover

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (6)

Algorithms for finding disjoint path covers in unit interval graphs ⋮ Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph ⋮ A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs ⋮ Paired many-to-many disjoint path covers of hypertori ⋮ 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
• Unnamed Item
• Simple linear time recognition of unit interval graphs
• Recognizing and representing proper interval graphs in parallel using merging and sorting
• Linear algorithm for optimal path cover problem on interval graphs
• A linear time recognition algorithm for proper interval graphs
• Finding Hamiltonian circuits in proper interval graphs
• Finding Hamiltonian circuits in interval graphs
• Hamiltonian circuits in interval graph generalizations
• The directed subgraph homeomorphism problem
• Disjoint paths in graphs
• Paths in interval graphs and circular arc graphs
• Optimal path cover problem on block graphs and bipartite permutation graphs
• A time-optimal solution for the path cover problem on cographs.
• Parallel algorithms for Hamiltonian problems on quasi-threshold graphs
• An efficient parallel strategy for the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs
• Graph minors. XIII: The disjoint paths problem
• HAMILTONian circuits in chordal bipartite graphs
• Optimal greedy algorithms for indifference graphs
• Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
• A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
• A Polynomial Solution to the Undirected Two Paths Problem
• On the Computational Complexity of Combinatorial Problems
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Topics in Intersection Graph Theory
• Graph Classes: A Survey
• Computing and Combinatorics
• A linear‐time algorithm for the k‐fixed‐endpoint path cover problem on cographs

This page was built for publication: A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs