+91 8617752708

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.

Article Information


(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.

(2) Anonymous.

(3) Anonymous

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.

Keywords :

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/5816

Review History    Comments

Our Contacts

Guest House Road, Street no - 1/6,
Hooghly, West Bengal,

+91 8617752708


Third Floor, 207 Regent Street
London, W1B 3HH,

+44 20-3031-1429