Input-Output Decomposition of Dynamic Systems is NP-Complete

Robert E. Tarjan

doi:10.1109/TAC.1984.1103657

Input-Output Decomposition of Dynamic Systems is NP-Complete

Robert E. Tarjan

Research output: Contribution to journal › Article › peer-review

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 language	English (US)
Pages (from-to)	863-864
Number of pages	2
Journal	IEEE Transactions on Automatic Control
Volume	29
Issue number	9
DOIs	https://doi.org/10.1109/TAC.1984.1103657
State	Published - 1984
Externally published	Yes

All Science Journal Classification (ASJC) codes

Control and Systems Engineering
Computer Science Applications
Electrical and Electronic Engineering

Access to Document

10.1109/TAC.1984.1103657

Cite this

@article{7f065e7653004d2b8b3b96cc378a1b66,

title = "Input-Output Decomposition of Dynamic Systems is NP-Complete",

abstract = "Pichai, Sezar, and {\AA} 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.",

author = "Tarjan, {Robert E.}",

year = "1984",

doi = "10.1109/TAC.1984.1103657",

language = "English (US)",

volume = "29",

pages = "863--864",

journal = "IEEE Transactions on Automatic Control",

issn = "0018-9286",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "9",

}

TY - JOUR

T1 - Input-Output Decomposition of Dynamic Systems is NP-Complete

AU - Tarjan, Robert E.

PY - 1984

Y1 - 1984

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84912728050&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84912728050&partnerID=8YFLogxK

U2 - 10.1109/TAC.1984.1103657

DO - 10.1109/TAC.1984.1103657

M3 - Article

AN - SCOPUS:84912728050

SN - 0018-9286

VL - 29

SP - 863

EP - 864

JO - IEEE Transactions on Automatic Control

JF - IEEE Transactions on Automatic Control

IS - 9

ER -

Input-Output Decomposition of Dynamic Systems is NP-Complete

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this