Path cover problems with length cost

DOI10.1007/978-3-030-96731-4_32MaRDI QIDQ2154120zbMATH OpenOpenAlexFDO

Authors Kenya Kobayashi, Eiji Miyano, Toshiki Saitoh, Akira Suzuki, Tadatoshi Utashima, Tsuyoshi Yagita, Guohui Lin

Publication date 13 July 2022

Full work available at URL https://doi.org/10.1007/978-3-030-96731-4_32

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A local search \(4/3\)-approximation algorithm for the minimum 3-path partition problem
• A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two
• Complexity of Finding Embeddings in a k-Tree
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Nontrivial path covers of graphs: existence, minimization and maximization
• On the \(k\)-path partition of graphs.
• On the Complexity of General Graph Factor Problems
• Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph
• Planar Formulae and Their Uses
• The existence of \(P_{\geq3}\)-factor covered graphs
• The path partition problem and related problems in bipartite graphs

Cited in

(6)

• Approximation algorithms for covering vertices by long paths
• An approximation algorithm for covering vertices by \(4^+\)-paths
• Approximation algorithms for non-sequential star packing problems
• 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

This page was built for publication: Path cover problems with length cost

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