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

DOI10.1016/J.TCS.2009.11.003MaRDI QIDQ2268855zbMATH OpenOpenAlexFDO

Authors Katerina Asdre, Stavros D. Nikolopoulos

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

fixed-endpoint path coverlinear-time algorithmspath coverperfect graphsproper interval graphs

Mathematics Subject Classification ID

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

Recommendations

• The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
• An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs
• An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs
• A linear‐time algorithm for the k‐fixed‐endpoint path cover problem on cographs
• The 2-Terminal-Set Path Cover Problem and Its Polynomial Solution on Cographs

Cites work

• A Fully dynamic algorithm for recognizing and representing proper interval graphs
• A linear time recognition algorithm for proper interval graphs
• A linear‐time algorithm for the k‐fixed‐endpoint path cover problem on cographs
• A Polynomial Solution to the Undirected Two Paths Problem
• A time-optimal solution for the path cover problem on cographs.
• An efficient parallel strategy for the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs
• Computing and Combinatorics
• Disjoint paths in graphs
• Finding Hamiltonian circuits in interval graphs
• Finding Hamiltonian circuits in proper interval graphs
• Graph Classes: A Survey
• Graph minors. XIII: The disjoint paths problem
• HAMILTONian circuits in chordal bipartite graphs
• Hamiltonian circuits in interval graph generalizations
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3706451 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Linear algorithm for optimal path cover problem on interval graphs
• Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
• On the Computational Complexity of Combinatorial Problems
• Optimal greedy algorithms for indifference graphs
• Optimal path cover problem on block graphs and bipartite permutation graphs
• Parallel algorithms for Hamiltonian problems on quasi-threshold graphs
• Paths in interval graphs and circular arc graphs
• Recognizing and representing proper interval graphs in parallel using merging and sorting
• Simple linear time recognition of unit interval graphs
• The directed subgraph homeomorphism problem
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Topics in Intersection Graph Theory

Cited in

(21)

• The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
• Parameterized complexity of \((A,\ell)\)-path packing
• Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph
• Algorithms for finding disjoint path covers in unit interval graphs
• A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs
• An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs
• The 2-Terminal-Set Path Cover Problem and Its Polynomial Solution on Cographs
• Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs
• A linear‐time algorithm for the k‐fixed‐endpoint path cover problem on cographs
• An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs
• Approximation algorithms for covering vertices by long paths
• An approximation algorithm for covering vertices by \(4^+\)-paths
• Semi-proper interval graphs
• Covering vertices by 4^+-paths: a simpler local search coupled with a more delicate amortization
• Approximation algorithms for the maximum path cover problem using long paths
• Approximately covering vertices by order-5 or longer paths
• Approximately covering vertices by order-5 or longer paths
• An improved approximation algorithm for covering vertices by 4^+-paths
• Computing Hamiltonian paths with partial order restrictions
• Paired many-to-many disjoint path covers of hypertori
• A graph width perspective on partially ordered Hamiltonian paths and cycles ii: vertex and edge deletion numbers

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2268855)