文章基本信息

标题：Some Complexity Problems on Single Input Double Output Controllers
本地全文：下载
作者：Katalin M. Hangos ; Zsolt Tuza ; Anders Yeo 等
期刊名称：BRICS Report Series
印刷版ISSN：0909-0878
出版年度：2001
卷号：8
期号：18
出版社：Aarhus University
摘要：We investigate the time complexity of constructing single input double output state feedback controller structures, given the directed structure graph G of a system. Such a controller structure defines a restricted type of P3-partition of the graph G. A necessary condition (*) has been found and two classes of graphs have been identified where the search problem of finding a feasible P3- partition is polynomially solvable and, in addition, (*) is not only necessary but also sufficient for the existence of a P3-partition. It is shown further that the decision problem on two particular graph classes - defined in terms of forbidden subgraphs - remains NP- complete, but is polynomially solvable on the intersection of those two classes. Moreover, for every natural number m, a stabilizing structure with Single Input m-Output controllers can be found in polynomial time for the system in question, if it admits one.