EFFICIENT LEVEL-STRUCTURING ALGORITHM FOR LARGE SCALE SYSTEMS.

Modeling a physical system by a system digraph has been an efficient paradigm in fault diagnosis and structure identification in large scale systems. A level-structured system digraph illustrates the hierarchy of interconnections, and is a versatile tool in failure source identification and structural analysis. A straightforward implementation of the algorithm, based on the definition, has the upper bound time complex of O(n**3) and the lower bound time and space complexities of OMEGA (n**2), where n is the number of the nodes of the system digraph. We present an O(n plus e) algorithm, where e is the number of edges of the system digraph.