Minimum Area Layout of Series-Parallel Transistor Networks is NP-Hard

S. Chakravarty; Xin He; S. S. Ravi

doi:10.1109/43.87604

Minimum Area Layout of Series-Parallel Transistor Networks is NP-Hard

S. Chakravarty
, Xin He
, S. S. Ravi

Department of Computer Science and Engineering

SUNY Buffalo
University at Albany, SUNY

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

13 Scopus citations

Abstract

Functional cells are a physical realization of complex MOS gates. Efficient algorithms for minimizing the width of a functional cell are known. Every solution to the width minimization problem leads to a cell of a certain height. We show that, even for functional cells of complex MOS gates represented by series-parallel transistor networks, the problem of finding a solution of minimum width which also minimizes the height is NP-hard.

Original language	English
Pages (from-to)	943-949
Number of pages	7
Journal	IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume	10
Issue number	7
DOIs	https://doi.org/10.1109/43.87604
State	Published - Jul 1991

Keywords

Functional cells
height minimization
layout
NP-hard
series-parallel transistor net-
width minimization
works

Access to Document

10.1109/43.87604

Cite this

@article{a6562ef58e3141099686aaa8c71cc6e7,

title = "Minimum Area Layout of Series-Parallel Transistor Networks is NP-Hard",

abstract = "Functional cells are a physical realization of complex MOS gates. Efficient algorithms for minimizing the width of a functional cell are known. Every solution to the width minimization problem leads to a cell of a certain height. We show that, even for functional cells of complex MOS gates represented by series-parallel transistor networks, the problem of finding a solution of minimum width which also minimizes the height is NP-hard.",

keywords = "Functional cells, height minimization, layout, NP-hard, series-parallel transistor net-, width minimization, works",

author = "S. Chakravarty and Xin He and Ravi, \{S. S.\}",

year = "1991",

month = jul,

doi = "10.1109/43.87604",

language = "English",

volume = "10",

pages = "943--949",

journal = "IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems",

issn = "0278-0070",

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

number = "7",

}

TY - JOUR

T1 - Minimum Area Layout of Series-Parallel Transistor Networks is NP-Hard

AU - Chakravarty, S.

AU - He, Xin

AU - Ravi, S. S.

PY - 1991/7

Y1 - 1991/7

N2 - Functional cells are a physical realization of complex MOS gates. Efficient algorithms for minimizing the width of a functional cell are known. Every solution to the width minimization problem leads to a cell of a certain height. We show that, even for functional cells of complex MOS gates represented by series-parallel transistor networks, the problem of finding a solution of minimum width which also minimizes the height is NP-hard.

AB - Functional cells are a physical realization of complex MOS gates. Efficient algorithms for minimizing the width of a functional cell are known. Every solution to the width minimization problem leads to a cell of a certain height. We show that, even for functional cells of complex MOS gates represented by series-parallel transistor networks, the problem of finding a solution of minimum width which also minimizes the height is NP-hard.

KW - Functional cells

KW - height minimization

KW - layout

KW - NP-hard

KW - series-parallel transistor net-

KW - width minimization

KW - works

UR - https://www.scopus.com/pages/publications/0026186426

U2 - 10.1109/43.87604

DO - 10.1109/43.87604

M3 - Article

AN - SCOPUS:0026186426

SN - 0278-0070

VL - 10

SP - 943

EP - 949

JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

IS - 7

ER -

Minimum Area Layout of Series-Parallel Transistor Networks is NP-Hard

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this