کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420687 | 683968 | 2009 | 13 صفحه PDF | دانلود رایگان |
We investigate the time complexity of constructing single input double output state feedback controller structures, given the directed structure graph GG of a system. Such a controller structure defines a restricted type of P3P3-partition of the graph GG. A necessary condition (∗) is described and some classes of graphs are identified where the search problem of finding a feasible P3P3-partition is polynomially solvable and, in addition, (∗) is not only necessary but also sufficient for the existence of a P3P3-partition. It is also proved 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. The polynomial-time solvability of some further related problems is shown, too.
Journal: Discrete Applied Mathematics - Volume 157, Issue 5, 6 March 2009, Pages 1146–1158