Given a directed graph, we present and experimentally validate new heuristics to find good linear orderings of its vertices so to obtain Feedback Arc Sets which are minimal, i.e. such that none of the arcs can be reintroduced in the graph without disrupting acyclicity. We will also show that, in many cases, the newly proposed linear orderings along with an improved heuristic algorithm to reinsert eliminated arcs, which has a good polynomial upper bounds, produce, in fact, a minimum FAS.

Efficient Vertex Linear Orderings to Find Minimal Feedback Arc Sets (minFAS)

Cavallaro C.;Cutello V.;Pavone M.
2025-01-01

Abstract

Given a directed graph, we present and experimentally validate new heuristics to find good linear orderings of its vertices so to obtain Feedback Arc Sets which are minimal, i.e. such that none of the arcs can be reintroduced in the graph without disrupting acyclicity. We will also show that, in many cases, the newly proposed linear orderings along with an improved heuristic algorithm to reinsert eliminated arcs, which has a good polynomial upper bounds, produce, in fact, a minimum FAS.
2025
9783031756221
9783031756238
Experimental Analysis
Heuristics
Minimal Feedback Arc Set
Optimization Problem
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/20.500.11769/660549
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact