Approximation algorithms for covering vertices by long paths

DOI10.4230/LIPICS.MFCS.2022.53MaRDI QIDQ6584055zbMATH OpenFDO

Authors Mingyang Gong, Jing Fan, Guohui Lin, Eiji Miyano

Publication date 6 August 2024

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2022.53

zbMATH Keywords

\(k\)-pathamortized analysisapproximation algorithmlocal improvementpath cover

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(8)

• An approximation algorithm for covering vertices by \(4^+\)-paths
• Approximation algorithms for non-sequential star packing problems
• Covering vertices by 4^+-paths: a simpler local search coupled with a more delicate amortization
• Approximation algorithms for the maximum path cover problem using long paths
• Approximately covering vertices by order-5 or longer paths
• Approximately covering vertices by order-5 or longer paths
• An improved approximation algorithm for covering vertices by 4^+-paths
• Approximation algorithms for non-sequential star packing problems

This page was built for publication: Approximation algorithms for covering vertices by long paths

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