A survey on vertex cover P_k problem

DOI10.13878/J.CNKI.JNUIST.2017.05.001zbMATH Open1399.05184MaRDI QIDQ4640752FDOQ4640752

Jingyu Hua, Limin Wang

Publication date: 25 May 2018

Recommendations

• Efficient algorithm for the vertex cover \(P_k\) problem on cacti
• A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem
• A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• The vertex cover \(P_3\) problem in cubic graphs
• A 2-approximation algorithm for the vertex cover \(P_{4}\) problem in cubic graphs

zbMATH Keywords

approximation algorithmsexact algorithmsparameter algorithmsvertex cover \({P_k}\)

Mathematics Subject Classification ID

Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

This page was built for publication: A survey on vertex cover \({P_k}\) problem

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