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.
2023
Big Data
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/588649
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact