A 21/16-Approximation for the Minimum 3-Path Partition Problem

DOI10.4230/LIPICS.ISAAC.2019.46MaRDI QIDQ5875609zbMATH OpenOpenAlexFDO

Authors Yong Chen, Randy Goebel, Bing Su, Weitian Tong, Yao Xu, An Zhang

Publication date 3 February 2023

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2019/11542/pdf/LIPIcs-ISAAC-2019-46.pdf/

zbMATH Keywords

\(3\)-path partitionamortized analysisapproximation algorithmexact set coverlocal search

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cited in

(11)

• A local search 4/3-approximation algorithm for the minimum 3-path partition problem
• Path cover problems with length cost
• A local search algorithm for the k-path partition problem
• Approximating the directed path partition problem
• Approximation algorithms for covering vertices by long paths
• Improved approximation algorithms for the \(k\)-path partition problem
• An improved approximation algorithm for the minimum k-star partition problem
• Path cover using only short paths
• Directed path partition problem on directed acyclic graphs
• An improved approximation algorithm for the minimum 4-star partition problem
• Approximately partitioning vertices into short paths

This page was built for publication: A 21/16-Approximation for the Minimum 3-Path Partition Problem

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