Quick Menu

Upcoming Journals

British Journal of Mathematics & Computer Science

British Journal of Mathematics & Computer Science, ISSN: 2231-0851,Vol.: 4, Issue.: 5 (01-15 March)


Original Research Article


Applications of Loop Trees



Ward Douglas Maurer1*

1Department of Computer Science, George Washington University, Washington, DC 20052, USA.




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    Article Metrics


DOI : 10.9734/BJMCS/2014/5816

Review History    Comments

Search this site

Advanced Search

Announcement & News

ISI Thomson Reuters selected British Journal of Pharmaceutical Research for Emerging Sources Citation Index

We are delighted to inform that ISI Thomson Reuters selected British Journal of Pharmaceutical Resea...

SCOPUS selected Annual Research & Review in Biology (ARRB)

We are delighted to inform that famous indexing organization SCOPUS (from Elsevier) selected  A...

Index Copernicus Evaluation Result Released

We are delighted to inform that Index Copernicus (a leading indexing organization from Pol...

Journal Repository (JR): Permanent Digital Archiving of SDI journals

SDI is happy to announce that all our journals are now permanently archived in Journal Repository (J...

SDI journal got 35th ranking in Publons

We are delighted to announce (as of 04/01/2016) that British Journal of Medicine and Medical Re...

Growth of SDI and world publication market

As of 2014, total 25,064 journals are competing in World market of journal publication. In 2011, tot...

Science (IF: 31) report confirmed the high standard of SDI journal

As per a recent report (Link) of Science journal (present Impact factor 31), one of our journal (Bri...

SDI introduced Post-publication peer review by its comment section

SDI journals encourage Post-publication peer review by its comment section   Policy details a...

SDI promotes transparent Advanced OPEN peer review

We have migrated to transparent and toughest ‘Advanced OPEN peer review’ system (...


  • No Awards listed.

Browser Compatibility : Mozila firefox, Google Crome and IE 7 & above. Creative Commons License Terms & Condition   |   Privacy Policy   |   Join Us   |   Help   |   Contact Us
© Copyright 2010-2018, SCIENCEDOMAIN international. All rights reserved.