ON THE STRUCTURE OF DIRECTED GRAPHS WITH APPLICATIONS: A Rapprochement with Systems Theory Part II

Abstract

In Part I of this paper¹, a rapprochement with system theory has been established for the study of digraph structure.

In this Part II we first extend the basic results of Part I to the structure of composite digraphs- Then the decomposition of a digraph according to its internal composition/interaction will be explored using the concept of subsystem interaction. An algorithm is given for closed/irreducible closed subgraph identification and decomposition. Applications to computer systems, Markov chains, and to control and dynamic systems are discussed. A new canonical form for large-scale decentralized control/estimation is proposed.

Additional information

Notes on contributors

KUOTING M. TAO

Kuoling Mike Tao is a Senior Lead Systems Engineer of General Electric Company. San Jose, California, responsible for control systems design and other systems engineering functions, lie was born in Nanking, China, on October 30, 1947; received B.S. and M.S. degrees in Nuclear Engineering from National Tsing Hua University, Taiwan, China, in 1968 and 1970, respectively. He also holds an M.S. degree (1973) in Operations Research from Georgia Institute of Technology, Atlanta, Georgia, where he was a Ph.D. candidate in Systems Engineering. Mr. Tao.started serious studies on dynamic systems while, al Tsing Hua. doing Masterapos;s research on random-parameter modelling of nuclear reactor kinetics and its effect on the noise spectrum. During 1971-1972, he was enrolled in the Sc.D program in Control Systems Science and Engineering, Washington University, St. Louis. Later, at Georgia Institute of Technology, he was introduced to the concept of General Systems by Dr. T. G. Windeknecht.Aside from General Electric, Mr. Taos industrial experience includes working with Northrop, Huntsville, Alabama (1974 1975). on space shuttle related dynamic modelling, analysis and control. He also applied O.R. techniques to shuttle mission planning. Mr. Tito's current research interests unclude: combined classical and modern approaches to control, estimation, and identification, robust and adaptive systems design, and applying general systems concepts to computer systems and certain non-traditional areas. He is a member of the IEEE Conlrol Systems and Computer Societies.

PEI HSIA

Pei Hsia is an associate professor in the Computer Science Department of the University of Alabama in Huntsville. Earlier, he was employed by Logicon, Inc., in Los Angeles,California. His major researchinterests are programming methodologies, programming languages, operating systems, and computational complexity. Hsia holds a BS in mathematics from the National Taiwan University, Taipei, Taiwan, Republic of China, as well as an MS in computer science from Pennsylvania Slate University, State College. He received the PhD in computer science from the University of Texas, Austin, in 1972. He is a member of the IEEE Computer Society and ACM.