Path cover problems with length cost

DOI10.1007/S00453-023-01106-2MaRDI QIDQ6069927zbMATH OpenOpenAlexFDO

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

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 algorithmNP-hardnesspath cover problemplanar bipartite graphsubcubic graphtreewidth

Mathematics Subject Classification ID

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

Cites work

• A 21/16-Approximation for the Minimum 3-Path Partition Problem
• 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
• An improved approximation algorithm for the minimum 3-path partition problem
• Complexity of Finding Embeddings in a k-Tree
• Covering the vertices of a graph by vertex-disjoint paths
• 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
• Parameterized algorithms
• 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
• Tree decompositions of graphs: saving memory in dynamic programming

Cited in

(12)

• Approximation algorithms for covering vertices by long paths
• Approximation algorithms for non-sequential star packing problems
• 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
• Path cover using only short paths
• Approximately covering vertices by order-5 or longer paths
• Approximation algorithms for the k^+-star packing problem
• An improved approximation algorithm for covering vertices by 4^+-paths
• Approximation algorithms for non-sequential star packing problems
• Unpaired set-to-set disjoint path routings in recursive match networks
• Approximately partitioning vertices into short 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 Q6069927)