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

Yehoshua Perl, Marc Snir

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish (US)
Title of host publicationUnknown Host Publication Title
PublisherPrinceton Univ
Pages80-84
Number of pages5
StatePublished - 1982
Externally publishedYes

Fingerprint

Networks (circuits)
Dynamic programming
Polynomials

ASJC Scopus subject areas

  • Engineering(all)

Cite this

Perl, Y., & Snir, M. (1982). CIRCUIT PARTITIONING WITH SIZE AND CONNECTION CONSTRAINTS (EXTENDED ABSTRACT). In Unknown Host Publication Title (pp. 80-84). Princeton Univ.

CIRCUIT PARTITIONING WITH SIZE AND CONNECTION CONSTRAINTS (EXTENDED ABSTRACT). / Perl, Yehoshua; Snir, Marc.

Unknown Host Publication Title. Princeton Univ, 1982. p. 80-84.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Perl, Y & Snir, M 1982, CIRCUIT PARTITIONING WITH SIZE AND CONNECTION CONSTRAINTS (EXTENDED ABSTRACT). in Unknown Host Publication Title. Princeton Univ, pp. 80-84.
Perl Y, Snir M. CIRCUIT PARTITIONING WITH SIZE AND CONNECTION CONSTRAINTS (EXTENDED ABSTRACT). In Unknown Host Publication Title. Princeton Univ. 1982. p. 80-84
Perl, Yehoshua ; Snir, Marc. / CIRCUIT PARTITIONING WITH SIZE AND CONNECTION CONSTRAINTS (EXTENDED ABSTRACT). Unknown Host Publication Title. Princeton Univ, 1982. pp. 80-84
@inproceedings{32688cb935a5413fbd1a8c349a7c25dc,
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",
booktitle = "Unknown Host Publication Title",
publisher = "Princeton Univ",

}

TY - GEN

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 - Conference contribution

SP - 80

EP - 84

BT - Unknown Host Publication Title

PB - Princeton Univ

ER -