A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem

DOI10.1137/S0895480196305124zbMath0932.68054MaRDI QIDQ4699157

Toshihiro Fujito, Vineet Bafna, Piotr Berman

Publication date: 23 November 1999

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

approximation algorithm; performance guarantee; feedback vertex set problem; local ratio theorem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C27: Combinatorial optimization

05C38: Paths and cycles

05C85: Graph algorithms (graph-theoretic aspects)