CIRCUIT PARTITIONING WITH SIZE AND CONNECTION CONSTRAINTS (EXTENDED ABSTRACT).

Yehoshua Perl; Marc Snir

CIRCUIT PARTITIONING WITH SIZE AND CONNECTION CONSTRAINTS (EXTENDED ABSTRACT).

Research output: Contribution to conference › Paper › peer-review

Abstract

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 language	English (US)
Pages	80-84
Number of pages	5
State	Published - 1982
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Engineering

Cite this

@conference{41ef5382ce8340c18a1610ac8173a715,

title = "CIRCUIT PARTITIONING WITH SIZE AND CONNECTION CONSTRAINTS (EXTENDED ABSTRACT).",

abstract = "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.",

author = "Yehoshua Perl and Marc Snir",

year = "1982",

language = "English (US)",

pages = "80--84",

}

TY - CONF

T1 - CIRCUIT PARTITIONING WITH SIZE AND CONNECTION CONSTRAINTS (EXTENDED ABSTRACT).

AU - Perl, Yehoshua

AU - Snir, Marc

PY - 1982

Y1 - 1982

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

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

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

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

M3 - Paper

AN - SCOPUS:0020234155

SP - 80

EP - 84

ER -

CIRCUIT PARTITIONING WITH SIZE AND CONNECTION CONSTRAINTS (EXTENDED ABSTRACT).

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this