Input-Output Decomposition of Dynamic Systems is NP-Complete

Research output: Contribution to journalArticle

5 Scopus citations

Abstract

Pichai, Sezar, and Å iljak have studied a decomposition technique for acyclic graphs, called input–output decomposition, that simplifies the analysis of dynamic systems. We show that the problem of determining whether a given graph is decomposable is NP-complete. Since this makes the existence of a polynomial-time decomposition algorithm unlikely, the possible benefits of having an input–output decomposition may be outweighed by the difficulty of finding one.

Original languageEnglish (US)
Pages (from-to)863-864
Number of pages2
JournalIEEE Transactions on Automatic Control
Volume29
Issue number9
DOIs
StatePublished - Jan 1 1984
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Input-Output Decomposition of Dynamic Systems is NP-Complete'. Together they form a unique fingerprint.

  • Cite this