The complexity of minimizing wire lengths in VLSI layouts

Sandeep N. Bhatt; Stavros S. Cosmadakis

doi:10.1016/0020-0190(87)90173-6

The complexity of minimizing wire lengths in VLSI layouts

Sandeep N. Bhatt
, Stavros S. Cosmadakis

Massachusetts Institute of Technology

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

91 Scopus citations

Abstract

Deciding if a graph has a VLSI layout with a specified maximum edge length is NP-complete.

Original language	English
Pages (from-to)	263-267
Number of pages	5
Journal	Information Processing Letters
Volume	25
Issue number	4
DOIs	https://doi.org/10.1016/0020-0190(87)90173-6
State	Published - 17 Jun 1987

Keywords

NP-completeness
VLSI layout
wire length

Access to Document

10.1016/0020-0190(87)90173-6

Cite this

@article{105fb94c6a554646b80fb44588c5f3f0,

title = "The complexity of minimizing wire lengths in VLSI layouts",

abstract = "Deciding if a graph has a VLSI layout with a specified maximum edge length is NP-complete.",

keywords = "NP-completeness, VLSI layout, wire length",

author = "Bhatt, \{Sandeep N.\} and Cosmadakis, \{Stavros S.\}",

year = "1987",

month = jun,

day = "17",

doi = "10.1016/0020-0190(87)90173-6",

language = "English",

volume = "25",

pages = "263--267",

number = "4",

}

TY - JOUR

T1 - The complexity of minimizing wire lengths in VLSI layouts

AU - Bhatt, Sandeep N.

AU - Cosmadakis, Stavros S.

PY - 1987/6/17

Y1 - 1987/6/17

N2 - Deciding if a graph has a VLSI layout with a specified maximum edge length is NP-complete.

AB - Deciding if a graph has a VLSI layout with a specified maximum edge length is NP-complete.

KW - NP-completeness

KW - VLSI layout

KW - wire length

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

UR - https://www.scopus.com/pages/publications/0023366780#tab=citedBy

U2 - 10.1016/0020-0190(87)90173-6

DO - 10.1016/0020-0190(87)90173-6

M3 - Article

AN - SCOPUS:0023366780

SN - 0020-0190

VL - 25

SP - 263

EP - 267

JO - Information Processing Letters

JF - Information Processing Letters

IS - 4

ER -

The complexity of minimizing wire lengths in VLSI layouts

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this