Some Complexity Problems on Single Input Double Output Controllers

Forfattere

  • Katalin M. Hangos
  • Zsolt Tuza
  • Anders Yeo

DOI:

https://doi.org/10.7146/brics.v8i18.20475

Resumé

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.

Downloads

Publiceret

2001-05-18

Citation/Eksport

Hangos, K. M., Tuza, Z., & Yeo, A. (2001). Some Complexity Problems on Single Input Double Output Controllers. BRICS Report Series, 8(18). https://doi.org/10.7146/brics.v8i18.20475

Nummer

Nr. 18 (2001): RS-18 Some Complexity Problems on Single Input Double Output Controllers

Sektion

Artikler

Licens

Authors who publish with this journal agree to the following terms:

    1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

    1. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

  1. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).