Polynomial-time algorithms for \textsc{Path Cover} on trees and graphs of bounded treewidth

DOI10.1007/978-3-031-83438-7_13MaRDI QIDQ6969500zbMATH OpenFDO

Authors Florent Foucaud, Atrayee Majumder, Tobias Mömke, Aida Roshany-Tabrizi

Publication date 20 June 2025

Full work available at URL https://doi.org/10.1007/978-3-031-83438-7_13

zbMATH Keywords

path covertreestreewidth

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Algorithms in computer science (68Wxx)

Cites work

• A linear algorithm for the Hamiltonian completion number of a tree
• A single-exponential time 2-approximation algorithm for treewidth
• An optimal path cover algorithm for cographs
• Finding a minimum path cover of a distance-hereditary graph in polynomial time
• Graph minors. XIII: The disjoint paths problem
• scientific article; zbMATH DE number 3694608 (Why is no real title available?)
• scientific article; zbMATH DE number 3465355 (Why is no real title available?)
• scientific article; zbMATH DE number 3467157 (Why is no real title available?)
• scientific article; zbMATH DE number 3404271 (Why is no real title available?)
• Introduction to algorithms.
• LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs
• On Path Cover Problems in Digraphs and Applications to Program Testing
• Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow
• Parameterized algorithms
• Parameterizing path partitions
• Path covering problems and testing of printed circuits
• Path partition for graphs with special blocks
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Sparsifying, shrinking and splicing for minimum path cover in parameterized linear time
• The Fine Details of Fast Dynamic Programming over Tree Decompositions
• Treewidth. Computations and approximations
• Vertex covering by paths on trees with its applications in machine translation

Cited in

(1)

• Covering and partitioning of split, chain and cographs with isometric paths

This page was built for publication: Polynomial-time algorithms for \textsc{Path Cover} on trees and graphs of bounded treewidth

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