Input-output decomposition of dynamic systems is NP-complete

DOI10.1109/TAC.1984.1103657zbMATH Open0563.93010OpenAlexW2046235602MaRDI QIDQ3677575FDOQ3677575

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

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

zbMATH Keywords

NP-completeacyclic graphsinput-output decomposition

Mathematics Subject Classification ID

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

Cited In (3)

• Sequential LQG optimization of hierarchically structured systems
• Title not available (Why is that?)
• A hard problem that is almost always easy

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)