A NOTE ON APPROXIMATION OF THE VERTEX COVER AND FEEDBACK VERTEX SET PROBLEMS - UNIFIED APPROACH

Authors
FUJITO T
Citation
T. Fujito, A NOTE ON APPROXIMATION OF THE VERTEX COVER AND FEEDBACK VERTEX SET PROBLEMS - UNIFIED APPROACH, Information processing letters, 59(2), 1996, pp. 59-63
Citations number
9
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
59
Issue
2
Year of publication
1996
Pages
59 - 63
Database
ISI
SICI code
0020-0190(1996)59:2<59:ANOAOT>2.0.ZU;2-R
Abstract
We consider the vertex cover and feedback vertex set problems for undi rected graphs, and show that they are structurally closely related via the standard vector spaces associated with the graphs. This observati on will then be used to demonstrate that these two problems can be eff iciently approximated within a same constant factor of 2 by essentiall y the same heuristics.