Some complexity problems on single input double output controllers

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 P 3 -partition of the graph G . A necessary condition (∗) is described and so...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2009-03, Vol.157 (5), p.1146-1158
Main Authors: Hangos, K.M., Tuza, Zs, Yeo, A.
Format: Article
Language:English
Subjects:
[formula omitted]-factor
Algorithmics. Computability. Computer arithmetics
Applied sciences
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Directed graph
Exact sciences and technology
Graph theory
Hall condition
Information retrieval. Graph
Mathematics
Polynomial algorithm
Sciences and techniques of general use
State feedback controller
Structural process control
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 P 3 -partition of the graph G . A necessary condition (∗) is described and some classes of graphs are identified where the search problem of finding a feasible P 3 -partition is polynomially solvable and, in addition, (∗) is not only necessary but also sufficient for the existence of a P 3 -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.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2008.03.028