Showing math.COShow all
2 papers · 1 filter
math.CO2024
Asymptotic Lower Bounds for the Feedback Arc Set Problem in Random Graphs
Harvey Diamond, Mark Kon, Louise Raphael
Given a directed graph, the Minimum Feedback Arc Set (FAS) problem asks for a minimum (size) set of arcs in a directed graph, which, when removed, results in an acyclic graph. In a…
math.CO2024
Asymptotics of the Minimal Feedback Arc Set in Erdős-Rényi Graphs
Harvey Diamond, Mark Kon, Louise Raphael
Given a directed graph, the Minimal Feedback Arc Set (FAS) problem asks for a minimal set of arcs which, when removed, results in an acyclic graph. Equivalently, the FAS problem as…