An improved approximation algorithm for the minimum 3-path partition problem

DOI10.1007/s10878-018-00372-zzbMath1425.90087OpenAlexW2908273849WikidataQ128647257 ScholiaQ128647257MaRDI QIDQ2424798

Yao Xu, Randy Goebel, An Zhang, Yong Chen, Bing Su, Guo-Hui Lin

Publication date: 25 June 2019

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-018-00372-z

zbMATH Keywords

approximation algorithmpath cover\(k\)-set coveramortized analysis\(k\)-path partition

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (6)

Approximation algorithms for the directed path partition problems ⋮ A local search algorithm for the \(k\)-path partition problem ⋮ Approximating the directed path partition problem ⋮ Path cover problems with length cost ⋮ Approximation algorithms for some minimum postmen cover problems ⋮ A local search 4/3-approximation algorithm for the minimum 3-path partition problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some results on graphs without long induced paths
• Approximation algorithms for combinatorial problems
• \(k\)-path partitions in trees
• Maximum skew-symmetric flows and matchings
• The path partition problem and related problems in bipartite graphs
• A threshold of ln n for approximating set cover
• Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow
• Star Partitions of Perfect Graphs
• Approximating the Unweighted k-Set Cover Problem: Greedy Meets Local Search

This page was built for publication: An improved approximation algorithm for the minimum 3-path partition problem