British Journal of Mathematics & Computer Science, ISSN: 2231-0851,Vol.: 4, Issue.: 5 (01-15 March)
Applications of Loop Trees
Ward Douglas Maurer1* 1Department of Computer Science, George Washington University, Washington, DC 20052, USA.
Ward Douglas Maurer1*
1Department of Computer Science, George Washington University, Washington, DC 20052, USA.
(1) Nor Azizah M. Yacob, Faculty of Computer and Mathematical Sciences, University of MARA Technology, Pahang, Malaysia
(1) Mugurel Ionut Andreica, Politehnica University of Bucharest, Romania.
Complete Peer review History:http://www.sciencedomain.org/review-history/2624
Aims: In a previous paper we have obtained a result which provides a new way to consider structured programs. Any directed graph whatsoever, according to this result, is a dag overlaid by a structured graph, with loops within loops in which no loops overlap. In such a structured graph, the only backward edges go from somewhere in a loop to the head of that loop. Crucial to this result is the construction of what we call a loop tree. As suggested by R. E. Tarjan, we here apply this result to three well-known situations. We also compare our decomposition method to two earlier such methods, one by Tarjan and one, much older, by Luce.
Methodology: We use the conventions of classical mathematics, in which sets and functions underlie all structures, such as directed graphs and loop trees, and in which all facts obtained in the course of the work are presented as theorems and lemmas, based on definitions and accompanied by valid proofs.
Results: We give a method of solving the single-source path expression problem for a reducible graph by examining its loop tree, which must be unique. We give a necessary and sufficient loop tree condition for a graph to have two edge-disjoint spanning trees, and a necessary and sufficient loop tree condition for a graph to have a feedback vertex.
Conclusion: The study of loop trees can be used to clarify many situations in the theory of directed graphs, in addition to the complete classification of directed graphs mentioned above.
Loop trees, path expressions, edge-disjoint spanning trees, feedback vertices, strongly connected components, wheels within wheels.
Full Article - PDF Page 612-666
DOI : 10.9734/BJMCS/2014/5816Review History Comments