DocumentCode :
1157333
Title :
Minimum Feedback Arc Sets for a Directed Graph
Author :
Younger, D.H.
Volume :
10
Issue :
2
fYear :
1963
fDate :
6/1/1963 12:00:00 AM
Firstpage :
238
Lastpage :
245
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 :
Feedback loop; Impedance; Switching circuits; Terminology; Topology; Tree graphs;
fLanguage :
English
Journal_Title :
Circuit Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9324
Type :
jour
DOI :
10.1109/TCT.1963.1082116
Filename :
1082116
Link To Document :
بازگشت