Input-output decomposition of dynamic systems is NP-complete

DOI10.1109/TAC.1984.1103657MaRDI QIDQ3677575zbMATH OpenOpenAlexFDO

Authors Robert E. Tarjan

Publication date 1984

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/tac.1984.1103657

zbMATH Keywords

acyclic graphsinput-output decompositionNP-complete

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Large-scale systems (93A15) Applications of graph theory to circuits and networks (94C15)

Recommendations

• NP-completeness of graph decomposition problems
• Recognizing decomposable graphs
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• General polynomial decomposition and the s-1-decomposition are NP-Hard
• Some complexity problems on single input double output controllers

Cited in

(3)

• scientific article; zbMATH DE number 3848931 (Why is no real title available?)
• A hard problem that is almost always easy
• Sequential LQG optimization of hierarchically structured systems

This page was built for publication: Input-output decomposition of dynamic systems is NP-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3677575)