Given a directed graph G = (V, E), we present a heuristic based algorithm to tackle the general Minimum Feedback Arc Problem with the goal of finding good (and often optimal) Feedback Arc Sets which are minimal, i.e. such that none of the arcs can be reintroduced in the graph without disrupting acyclicity. Our algorithm has a good polynomial upper bound which makes it suitable even when dealing with applications on large graphs useful on Big Data problems such as in Social Networks.
Effective Heuristics for Finding Small Minimal Feedback Arc Set Even for Large Graphs
Cavallaro C.;Cutello V.;Pavone M.
2023-01-01
Abstract
Given a directed graph G = (V, E), we present a heuristic based algorithm to tackle the general Minimum Feedback Arc Problem with the goal of finding good (and often optimal) Feedback Arc Sets which are minimal, i.e. such that none of the arcs can be reintroduced in the graph without disrupting acyclicity. Our algorithm has a good polynomial upper bound which makes it suitable even when dealing with applications on large graphs useful on Big Data problems such as in Social Networks.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.
