Back to Search
Start Over
Approximation Algorithms for Covering Vertices by Long Paths.
- Source :
-
Algorithmica . Aug2024, Vol. 86 Issue 8, p2625-2651. 27p. - Publication Year :
- 2024
-
Abstract
- Given a graph, the general problem to cover the maximum number of vertices by a collection of vertex-disjoint long paths seems to escape from the literature. A path containing at least k vertices is considered long. When k ≤ 3 , the problem is polynomial time solvable; when k is the total number of vertices, the problem reduces to the Hamiltonian path problem, which is NP-complete. For a fixed k ≥ 4 , the problem is NP-hard and the best known approximation algorithm for the weighted set packing problem implies a k-approximation algorithm. To the best of our knowledge, there is no approximation algorithm directly designed for the general problem; when k = 4 , the problem admits a 4-approximation algorithm which was presented recently. We propose the first (0.4394 k + O (1)) -approximation algorithm for the general problem and an improved 2-approximation algorithm when k = 4 . Both algorithms are based on local improvement, and their theoretical performance analyses are done via amortization and their practical performance is examined through simulation studies. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01784617
- Volume :
- 86
- Issue :
- 8
- Database :
- Academic Search Index
- Journal :
- Algorithmica
- Publication Type :
- Academic Journal
- Accession number :
- 178655131
- Full Text :
- https://doi.org/10.1007/s00453-024-01242-3