Back to Search
Start Over
Approximating the directed path partition problem.
- Source :
-
Information & Computation . Mar2024, Vol. 297, pN.PAG-N.PAG. 1p. - Publication Year :
- 2024
-
Abstract
- Given a digraph G = (V , E) , the k -path partition problem aims to find a minimum collection of vertex-disjoint directed paths, of order at most k , to cover all the vertices. The problem has various applications. Its special case on undirected graphs is NP-hard when k ≥ 3 , and has received much study recently from the approximation algorithm perspective. However, the general problem on digraphs is seemingly untouched in the literature. We fill the gap with the first k / 2 -approximation algorithm, based on a novel concept of enlarging walk to minimize the number of singletons. Secondly, for k = 3 , we define a second novel kind of enlarging walks to greedily reduce the number of 2-paths in the 3-path partition and propose an improved 13/9-approximation algorithm. Lastly, for any k ≥ 7 , we present an improved (k + 2) / 3 -approximation algorithm built on the maximum path-cycle cover followed by a careful 2-cycle elimination process. [ABSTRACT FROM AUTHOR]
- Subjects :
- *APPROXIMATION algorithms
*UNDIRECTED graphs
*DIRECTED graphs
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 08905401
- Volume :
- 297
- Database :
- Academic Search Index
- Journal :
- Information & Computation
- Publication Type :
- Academic Journal
- Accession number :
- 176010146
- Full Text :
- https://doi.org/10.1016/j.ic.2024.105150