Path cover problems with length cost

DOI10.1007/s00453-023-01106-2OpenAlexW4323317406MaRDI QIDQ6069927

Kenya Kobayashi, Akira Suzuki, Tsuyoshi Yagita, Tadatoshi Utashima, Eiji Miyano, Toshiki Saitoh, Guo-Hui Lin

Publication date: 17 November 2023

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-023-01106-2

zbMATH Keywords

approximation algorithmtreewidthNP-hardnesssubcubic graphplanar bipartite graphpath cover problem

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two
• On the \(k\)-path partition of graphs.
• Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph
• Nontrivial path covers of graphs: existence, minimization and maximization
• A local search \(4/3\)-approximation algorithm for the minimum 3-path partition problem
• The existence of \(P_{\geq3}\)-factor covered graphs
• An improved approximation algorithm for the minimum 3-path partition problem
• Tree decompositions of graphs: saving memory in dynamic programming
• The path partition problem and related problems in bipartite graphs
• Covering the vertices of a graph by vertex-disjoint paths
• On the Complexity of General Graph Factor Problems
• Complexity of Finding Embeddings in a k-Tree
• Planar Formulae and Their Uses
• Parameterized Algorithms
• A 21/16-Approximation for the Minimum 3-Path Partition Problem