P. Festa, P.M. Pardalos, and M.G.C. Resende
In Handbook of Combinatorial Optimization, D.-Z. Du and P.M. Pardalos, eds., Kluwer Academic Publishers, suppl. vol. A, pp. 209-259, 1999
ABSTRACT
This paper is a survey of feedback set problems (FSP).
FSP originated from applications in combinatorial circuit design, but
have found their way into numerous other applications, such as deadlock
prevention in operating systems, constraint satisfaction and Bayesian
inference in artificial intelligence, and graph theory. Directed
and undirected feedback vertex set problems are considered, including
polynomially solvable cases, approximation algorithms, exact algorithms,
and practical heuristics. The relationship between the feedback
vertex set and feedback arc set problems is examined and the state of
the art of feedback arc set problems is surveyed. Applications of
feedback set problems are described. Finally, future directions in
feedback set problem research are mapped out.
PostScript file of full paper
PDF file of full paper
Go back
Mauricio G.C. Resende's Home PageLast modified: 28 June 2002