An efficient algorithm for the vertex cover <i>P<sub>k</sub></i> problem on unicyclic graphs

PDF(899 KB)

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

管理与数理科学

An efficient algorithm for the vertex cover P_k 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 P_k problem on trees. Furthermore, an efficient algorithm for the vertex cover P_k problem on unicyclic graphs which can run in polynomial time is given.

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations

LI YuChao;TU JianHua. An efficient algorithm for the vertex cover P_k 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

Citation

Detail

Sections

Recommended

Abstract
Cite this article
References

Received	Revised	Published
2012-03-26	1900-01-01	2012-07-20
Issue Date
2012-07-20

Please choose a citation manager

Content to export

Abstract

Cite this article

{{custom_sec.title}}

{{custom_sec.title}}

References

{{custom_fnGroup.title_en}}

Footnotes

模态框（Modal）标题

Please choose a citation manager

Content to export

Abstract

Cite this article

{{custom_sec.title}}

{{custom_sec.title}}

References

{{custom_fnGroup.title_en}}

Footnotes