A survey on vertex cover P_k problem

DOI10.13878/J.CNKI.JNUIST.2017.05.001MaRDI QIDQ4640752zbMATH OpenFDO

Authors Jingyu Hua, Limin Wang

Publication date 25 May 2018

Full work available at URL https://doi.org/10.13878/J.CNKI.JNUIST.2017.05.001

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Recommendations

• Efficient algorithm for the vertex cover \(P_k\) problem on cacti
• A factor 2 approximation algorithm for the vertex cover P₃ 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

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)