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.
Feedback set problems / Festa, Paola; P. M., Pardalos; M. G. C., Resende. - STAMPA. - A:(2000), pp. 209-259.
Feedback set problems
FESTA, PAOLA;
2000
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
