Feedback Set Problems

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 Page
Last modified: 28 June 2002

Copyright Notice