Approximation algorithms for the maximum path cover problem using long paths

DOI10.1016/J.IC.2025.105378MaRDI QIDQ6884287zbMATH OpenFDO

Authors Mingyang Gong, Yong Chen, Zhi-Zhong Chen, Guohui Lin, Bing Su, Lusheng Wang

Publication date 15 December 2025

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2025.105378

zbMATH Keywords

approximation algorithmlocal searchpath coverpath-cycle coverrecursion

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Cites work

• 8/7-approximation algorithm for (1,2)-TSP
• 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
• Approximation algorithms for covering vertices by long paths
• Approximation algorithms for covering vertices by long paths
• Approximation algorithms for two-machine flow-shop scheduling with a conflict graph
• Finding triangle-free 2-factors in general graphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Nontrivial path covers of graphs: existence, minimization and maximization
• Path cover problems with length cost
• Path cover problems with length cost
• Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph
• The two-equal-disjoint path cover problem of matching composition network

This page was built for publication: Approximation algorithms for the maximum path cover problem using long paths

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