Premium
Circuit partitioning with size and connection constraints
Author(s) -
Perl Yehoshua,
Snir Marc
Publication year - 1983
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230130305
Subject(s) - connection (principal bundle) , tree (set theory) , polynomial , computer science , mathematics , algorithm , dynamic programming , time complexity , computational complexity theory , integer programming , mathematical optimization , combinatorics , mathematical analysis , geometry
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.