Computational Aspects of Graph Theoretic Methods in Control
Katalin Mária Hangos, Źsolt Tuza · Birkhäuser Boston eBooks · 1997
Various types of control problems related to distributed control system structure design, such as the analysis of structural controllability and observability, analysis of disturbance rejectivity, analysis of structural stability, design of distributed SISO (single input single output) controller system structures, and the design of distributed MIMO (multiple input multiple output) controller system structures, are described in the paper as algorithmic problems. Their equivalent graph theoretic problems and their algorithmic properties are also analysed. It is shown that the analysis of structural controllability and observability as well as structural disturbance rejectivity has polynomial time complexity. The structure design problems of stabilizing distributed SISO controller systems are polynomial, while in the general case of MIMO controllers the problems are harder. The same holds for distributed disturbance rejective controller system structure design problems: they may lead to polynomial graph theoretic problems in the SISO case, while they are NP-hard for the general MIMO case.