Circuit partitioning with size and connection constraints

Yehoshua Perl, Marc Snir

Research output: Contribution to journalArticlepeer-review


The problem of partitioning a circuit into subcomponents with constraints on the size of each subcomponent and the number of external connections is examined. While this problem is shown to be NP‐complete even for very restricted cases, a pseudo‐polynomial dynamic programming algorithm is given for the case where the circuit has a tree structure.

Original languageEnglish (US)
Pages (from-to)365-375
Number of pages11
Issue number3
StatePublished - 1983
Externally publishedYes

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications


Dive into the research topics of 'Circuit partitioning with size and connection constraints'. Together they form a unique fingerprint.

Cite this