The 2-Terminal-Set Path Cover Problem and Its Polynomial Solution on Cographs

DOI10.1007/978-3-540-69311-6_23MaRDI QIDQ3507334zbMATH OpenOpenAlexFDO

Authors Katerina Asdre, Stavros D. Nikolopoulos

Publication date 19 June 2008

Published in Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-69311-6_23

zbMATH Keywords

cographscomplement reducible graphsfixed-endpoint path coverlinear-time algorithmspath coverperfect graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• A linear‐time algorithm for the k‐fixed‐endpoint path cover problem on cographs
• A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs
• An optimal path cover algorithm for cographs
• The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
• scientific article; zbMATH DE number 1151806

Cites work

• A Linear Recognition Algorithm for Cographs
• A linear‐time algorithm for the k‐fixed‐endpoint path cover problem on cographs
• 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
• An optimal parallel solution for the path cover problem on \(P_{4}\)-sparse graphs
• An optimal path cover algorithm for cographs
• Complement reducible graphs
• Graph Classes: A Survey
• HAMILTONian circuits in chordal bipartite graphs
• Hamiltonicity in graphs with few \(P_ 4\)'s
• scientific article; zbMATH DE number 3859178 (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
• Modular decomposition and transitive orientation
• 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
• Solving the path cover problem on circular-arc graphs by using an approximation algorithm

Cited in

(5)

• 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
• A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs
• scientific article; zbMATH DE number 1151806 (Why is no real title available?)
• A linear‐time algorithm for the k‐fixed‐endpoint path cover problem on cographs

This page was built for publication: The 2-Terminal-Set Path Cover Problem and Its Polynomial Solution on Cographs

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