Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs

Vineet Bafna; Piotr Berman; Toshihiro Fujito

doi:10.1007/bfb0015417

Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs

Vineet Bafna, Piotr Berman, Toshihiro Fujito

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

44 Scopus citations

Abstract

We consider the weighted feedback vertex set problem for undirected graphs. It is shown that a generalized local ratio strategy leads to an efficient approximation with the performance guarantee of twice the optimal, improving the previous results for both weighted and unweighted cases. We further elaborate our approach to treat the case when graphs are of bounded degree, and show that it achieves even better performance, (formula presented), where ∆ is the maximum degree of graphs.

Original language	English (US)
Title of host publication	Algorithms and Computations - 6th International Symposium, ISAAC 1995, Proceedings
Editors	John Staples, Peter Eades, Naoki Katoh, Alistair Moffat
Publisher	Springer Verlag
Pages	142-151
Number of pages	10
ISBN (Print)	3540605738, 9783540605737
DOIs	https://doi.org/10.1007/bfb0015417
State	Published - 1995
Event	6th International Symposium on Algorithms and Computations, ISAAC 1995 - Cairns, Australia Duration: Dec 4 1995 → Dec 6 1995

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	1004
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	6th International Symposium on Algorithms and Computations, ISAAC 1995
Country/Territory	Australia
City	Cairns
Period	12/4/95 → 12/6/95

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/bfb0015417

Cite this

Bafna, V., Berman, P., & Fujito, T. (1995). Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs. In J. Staples, P. Eades, N. Katoh, & A. Moffat (Eds.), Algorithms and Computations - 6th International Symposium, ISAAC 1995, Proceedings (pp. 142-151). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1004). Springer Verlag. https://doi.org/10.1007/bfb0015417

Bafna, Vineet ; Berman, Piotr ; Fujito, Toshihiro. / Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs. Algorithms and Computations - 6th International Symposium, ISAAC 1995, Proceedings. editor / John Staples ; Peter Eades ; Naoki Katoh ; Alistair Moffat. Springer Verlag, 1995. pp. 142-151 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c2e6b2154b184076a33b9b211ef7a7d6,

title = "Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs",

abstract = "We consider the weighted feedback vertex set problem for undirected graphs. It is shown that a generalized local ratio strategy leads to an efficient approximation with the performance guarantee of twice the optimal, improving the previous results for both weighted and unweighted cases. We further elaborate our approach to treat the case when graphs are of bounded degree, and show that it achieves even better performance, (formula presented), where ∆ is the maximum degree of graphs.",

author = "Vineet Bafna and Piotr Berman and Toshihiro Fujito",

note = "Publisher Copyright: {\textcopyright} 1995, Springer-Verlag.; 6th International Symposium on Algorithms and Computations, ISAAC 1995 ; Conference date: 04-12-1995 Through 06-12-1995",

year = "1995",

doi = "10.1007/bfb0015417",

language = "English (US)",

isbn = "3540605738",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "142--151",

editor = "John Staples and Peter Eades and Naoki Katoh and Alistair Moffat",

booktitle = "Algorithms and Computations - 6th International Symposium, ISAAC 1995, Proceedings",

address = "Germany",

}

Bafna, V, Berman, P & Fujito, T 1995, Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs. in J Staples, P Eades, N Katoh & A Moffat (eds), Algorithms and Computations - 6th International Symposium, ISAAC 1995, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1004, Springer Verlag, pp. 142-151, 6th International Symposium on Algorithms and Computations, ISAAC 1995, Cairns, Australia, 12/4/95. https://doi.org/10.1007/bfb0015417

Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs. / Bafna, Vineet; Berman, Piotr; Fujito, Toshihiro.
Algorithms and Computations - 6th International Symposium, ISAAC 1995, Proceedings. ed. / John Staples; Peter Eades; Naoki Katoh; Alistair Moffat. Springer Verlag, 1995. p. 142-151 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1004).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs

AU - Bafna, Vineet

AU - Berman, Piotr

AU - Fujito, Toshihiro

PY - 1995

Y1 - 1995

N2 - We consider the weighted feedback vertex set problem for undirected graphs. It is shown that a generalized local ratio strategy leads to an efficient approximation with the performance guarantee of twice the optimal, improving the previous results for both weighted and unweighted cases. We further elaborate our approach to treat the case when graphs are of bounded degree, and show that it achieves even better performance, (formula presented), where ∆ is the maximum degree of graphs.

AB - We consider the weighted feedback vertex set problem for undirected graphs. It is shown that a generalized local ratio strategy leads to an efficient approximation with the performance guarantee of twice the optimal, improving the previous results for both weighted and unweighted cases. We further elaborate our approach to treat the case when graphs are of bounded degree, and show that it achieves even better performance, (formula presented), where ∆ is the maximum degree of graphs.

UR - http://www.scopus.com/inward/record.url?scp=84955602886&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84955602886&partnerID=8YFLogxK

U2 - 10.1007/bfb0015417

DO - 10.1007/bfb0015417

M3 - Conference contribution

AN - SCOPUS:84955602886

SN - 3540605738

SN - 9783540605737

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 142

EP - 151

BT - Algorithms and Computations - 6th International Symposium, ISAAC 1995, Proceedings

A2 - Staples, John

A2 - Eades, Peter

A2 - Katoh, Naoki

A2 - Moffat, Alistair

PB - Springer Verlag

T2 - 6th International Symposium on Algorithms and Computations, ISAAC 1995

Y2 - 4 December 1995 through 6 December 1995

ER -

Bafna V, Berman P, Fujito T. Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs. In Staples J, Eades P, Katoh N, Moffat A, editors, Algorithms and Computations - 6th International Symposium, ISAAC 1995, Proceedings. Springer Verlag. 1995. p. 142-151. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/bfb0015417

Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this