AbstractsComputer Science

A fast algorithm to determine minimality of strongly connected digraphs

by Jianping Zhu




Institution: University of Georgia
Department: Computer Science
Degree: MS
Year: 2002
Keywords: Digraph
Record ID: 1722593
Full text PDF: http://purl.galileo.usg.edu/uga_etd/zhu_jianping_200212_ms


Abstract

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.