.png){kind=icon}
.png){kind=icon}
Return
Approximation algorithms for the maximum path cover problem using long paths
.png){kind=icon}
OA
AI
DOI：10.1016/j.ic.2025.105378.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The problem studied in this paper is to find a collection of vertex-disjoint paths in a given graph G = (V, E) such that each path has length at least k, called a long path, and the total number of edges on these paths is maximized. The problem is NP-hard for any fixed k or when k is part of the input, by a reduction from the Hamiltonian path problem. Berman and Karpinski presented a 7/6-approximation algorithm for k = 1, but for a general k >= 2, there is no approximation algorithm directly for the problem. We present the first local search (0.4394k + O (1))-approximation algorithm for any fixed k >= 1, and a 1.4254-approximation algorithm for k = 2 built on top of a maximum triangle-free path-cycle cover. (c) 2025 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).
Keywords:
Path cover
Path-cycle cover
Local search
Recursion
Approximation algorithm
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
I
IF:
1
Papers:
79
Citations:
2.8K
View more organizations