General topological results on the construction of a minimum essential set of a directed graph
Aram Κ. Kevorkian · IEEE Transactions on Circuits and Systems · 1980
In this paper we present general topological results on the construction of a minimum essential set or minimum feedback vertex set of a directed graph. The results include all the existing topological rules that identify subsets of a minimum essential set as special cases. Moreover, we show how a class of topological results can be systematically generated by using the theory of strongly adjacent polygons. We use the topological results to provide an algorithm which constructs a minimal essential set of ann-vertex symmetric directed graph, a maximal stable set of an n-vertex undirected graph and an essential set of ann-vertex arbitrary directed graph in\theta (n^2)computation steps and such that these solutions are within a known tolerance of the optimal value.