A fast and effective heuristic for the feedback arc set problem
Eades, P., Lin, X. and Smyth, W.F. (1993) A fast and effective heuristic for the feedback arc set problem. Information Processing Letters, 47 (6). pp. 319-323.
*Subscription may be required
Let G=(V, A) denote a simple connected directed graph, and let n=|V|, m=|A|, where nt-1≤m≤(n2) A feedbackarc set (FAS) of G, denoted R(G), is a (possibly empty)set of arcs whose reversal makes G acyclic. A minimum feedbackarc set of G, denoted R∗(G), is a FAS of minimum cardinality r∗(G); the computation of R∗(G) is called the FASproblem. Berger and Shor have recently published an algorithm which, for a given digraph G, computes a FAS whose cardinality is at most m/2t-c1m/Δ1/2 where Δ is the maximum degree of G and c1 is a constant. Further, they exhibited an infinite class of graphs with the property that for every Gϵ and some constant c2, r∗(G)≥m /2t-c2m/Δ1/2. Thus the Berger-Shor algorithm provides, in a certain asymptotic sense, an optimal solution to the FAS problem. Unfortunately, the Berger-Shor algorithm is complicated and requires runni ng time O(mn). In this paper we present a simple FAS algorithm which guarantees a good (though not optimal) performance bound and executes in time O(m). Further, for the sparse graphs which arise frequently in graph drawing and other applications, our algorithm achieves the same asymptotic performance bound that Berger-Shor does.
|Publication Type:||Journal Article|
|Copyright:||© 2015 Elsevier B.V|
|Item Control Page|
Downloads per month over past year