Minimum Feedback Arc and Vertex Sets of a Directed Graph
- 1 December 1966
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Circuit Theory
- Vol. 13 (4) , 399-403
- https://doi.org/10.1109/tct.1966.1082620
Abstract
To determine a minimum set of arcs of an arbitrary directed graph which, if removed, leave the graph without directed circuits, is an outstanding problem in graph theory. A related problem is that of finding a minimum set of vertices which, if removed together with their incident arcs, leave the graph with no directed circuits. A closed form solution of both problems is presented. The determination of those minimum sets for a graph with n vertices involves the expansion of an n-th order permanent and some algebraic manipulations of the resultant expression, subject to the absorption laws of Boolean algebra. The proposed procedure renders all possible solutions simultaneously.Keywords
This publication has 3 references indexed in Scilit:
- Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic ProblemsOperations Research, 1965
- On the degrees of the vertices of a directed graphJournal of the Franklin Institute, 1965
- Minimum Feedback Arc Sets for a Directed GraphIEEE Transactions on Circuit Theory, 1963