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.

 

Abstracts

 

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

Index Copernicus Value of British Journal of Medicine and Medical Research

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

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

Publication and site statistics (up to Sept, 2015)

  Number of submission: 22181 (Total up to Sept, 2015) Number of published paper: 10949&n...

Index Medicus selected 15 SDI journals

We are delighted to inform that Index Medicus (IMSEAR) has selected following 15 SDI journals for in...

SCIENCEDOMAIN international received 5844 submissions in 2013

SCIENCEDOMAIN international is pleased to announce that it has received 5844 submissions in 2013, ac...



SCIENCEDOMAIN Awards

  • 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-2017, SCIENCEDOMAIN international. All rights reserved.