Approximating minimum feedback vertex sets in hypergraphs

Authors
Fujito, T
Citation
T. Fujito, Approximating minimum feedback vertex sets in hypergraphs, THEOR COMP, 246(1-2), 2000, pp. 107-116
Citations number
18
Categorie Soggetti
Computer Science & Engineering
Journal title
THEORETICAL COMPUTER SCIENCE
ISSN journal
03043975 → ACNP
Volume
246
Issue
1-2
Year of publication
2000
Pages
107 - 116
Database
ISI
SICI code
0304-3975(20000906)246:1-2<107:AMFVSI>2.0.ZU;2-Q
Abstract
The feedback vertex set problem for hypergraphs is considered and an effici ent approximation algorithm is presented. It is shown that an approximation factor of k is guaranteed when the cardinality of every hyperedge is bound ed by an integer k, generalizing the existing result for ordinary graphs. ( C) 2000 Elsevier Science B.V. All rights reserved.