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.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.