An efficient algorithm for the vertex cover Pk problem on unicyclic graphs

LI YuChao;TU JianHua

Journal of Beijing University of Chemical Technology ›› 2012, Vol. 39 ›› Issue (4) : 125-127.

PDF(899 KB)
Welcome to Journal of Beijing University of Chemical Technology, Today is July 29, 2025
Email Alert  RSS
PDF(899 KB)
Journal of Beijing University of Chemical Technology ›› 2012, Vol. 39 ›› Issue (4) : 125-127.
管理与数理科学

An efficient algorithm for the vertex cover Pk problem on unicyclic graphs

  • LI YuChao;TU JianHua
Author information +
History +

Abstract

Using the idea of a greedy algorithm, this paper presents an efficient algorithm for the vertex cover Pk problem on trees. Furthermore, an efficient algorithm for the vertex cover Pk problem on unicyclic graphs which can run in polynomial time is given.

Cite this article

Download Citations
LI YuChao;TU JianHua. An efficient algorithm for the vertex cover Pk problem on unicyclic graphs[J]. Journal of Beijing University of Chemical Technology, 2012, 39(4): 125-127

References

[1]ErdÖs P, Gallai T, Tuza Z. Covering the cliques of a graph with vertices[J]. Discrete Math, 1992, 108(1/2/3): 279-289.
[2]Bafna V, Berman P, Fujito T. A 2-approximation algorithm for the undirected feedback vertex set problem[J]. SIAM J Discrete Math, 1999, 12(3): 289-297. 
[3]Chudak F A, Goemans M X, Hochbaum D S, et al. A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs[J]. Operations Research Letters, 1998, 22(4/5): 111-118.
[4]Balachandran V, Nagavamsi P, Rangan C P. Clique transversal and clique independence on comparability graphs[J]. Information Processing Letters, 1996, 58(4): 181-184.
[5]Brešar B, Kardoš F, Katrenič J, et al. Minimum k-path vertex cover[J]. Discrete Applied Mathematics, 2011, 159(12): 1189-1195.
PDF(899 KB)

2429

Accesses

0

Citation

Detail

Sections
Recommended

/