A fast and effective heuristic for the feedback arc set problem

P. Eades; X. Lin; W.F. Smyth

doi:10.1016/0020-0190(93)90079-O

Back

Journal article

Open access

Peer reviewed

A fast and effective heuristic for the feedback arc set problem

P. Eades, X. Lin and W.F. Smyth

Information Processing Letters, Vol.47(6), pp.319-323

1993

DOI: https://doi.org/10.1016/0020-0190(93)90079-O

Files and links (2)

pdf

effective_heuristic.pdfDownload View

Author’s Version Open Access

url

Link to Published Version *Subscription may be requiredView

Abstract

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.

Details

Title: A fast and effective heuristic for the feedback arc set problem
Authors/Creators: P. Eades (Author/Creator) - University of Newcastle Australia
X. Lin (Author/Creator) - The University of Queensland
W.F. Smyth (Author/Creator) - McMaster University
Publication Details: Information Processing Letters, Vol.47(6), pp.319-323
Publisher: Elsevier BV
Identifiers: 991005543112107891
Murdoch Affiliation: Murdoch University
Language: English
Resource Type: Journal article

Metrics

1450 File views/ downloads

724 Record Views

122 Times Cited - Web of Science

InCites Highlights

These are selected metrics from InCites Benchmarking & Analytics tool, related to this output

Collaboration types: Domestic collaboration; International collaboration
Citation topics: 4 Electrical Engineering, Electronics & Computer Science; 4.182 Data Structures, Algorithms & Complexity; 4.182.125 Graph Theory
Web Of Science research areas: Computer Science, Information Systems
ESI research areas: Computer Science