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;
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.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11588/172342
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact