Minimum Feedback Arc Sets for a Directed Graph
- 1 June 1963
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Circuit Theory
- Vol. 10 (2) , 238-245
- https://doi.org/10.1109/tct.1963.1082116
Abstract
A minimum feedback arc set is, for a directed graph, a minimum set of arcs which if removed leaves the resultant graph free of directed loops. This paper establishes a relationship between these feedback arcs and order; in particular, such a minimum set of arcs is shown to be determined by a sequential ordering of the nodes which minimizes the number of arcs, each of which enters a node that precedes in the ordering the node it leaves. From this relationship are developed some simple characteristics of such sets, as well as properties of the sequential orderings by which these minimum sets are determined. These properties form the basis of an algorithm for finding minimum feedback arc sets.Keywords
This publication has 0 references indexed in Scilit: