A fast algorithm to determine minimality of strongly connected digraphs

by 1965- Zhu, Jianping

Abstract (Summary)
In this thesis, we consider the following problem: Given a strongly connected digraph G = (V, E), where V is the set of vertices and E is the set of edges , “is it a minimal strong connected digraph?”. A reducible edges e is one for which G?e is strongly connected. A minimal strongly connected digraph is one with no reducible edges. Our approach is to apply depth first search on G to generate a depth first search tree and the sets of back, forward, and cross edges. Then we determine if there are any reducible non-tree edges. If not, we then check if there are any reducible tree edges based on an algorithm for finding immediate dominators. We have implemented the algorithm and report experimental results that show the algorithm can handle large digraphs quickly.
Bibliographical Information:


School:The University of Georgia

School Location:USA - Georgia

Source Type:Master's Thesis



Date of Publication:

© 2009 All Rights Reserved.