The complexity of minimizing wire lengths in VLSI layouts

Sandeep N. Bhatt, Stavros S. Cosmadakis

Research output: Contribution to journalArticlepeer-review

88 Scopus citations

Abstract

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

Original languageEnglish
Pages (from-to)263-267
Number of pages5
JournalInformation Processing Letters
Volume25
Issue number4
DOIs
StatePublished - 17 Jun 1987

Keywords

  • NP-completeness
  • VLSI layout
  • wire length

Fingerprint

Dive into the research topics of 'The complexity of minimizing wire lengths in VLSI layouts'. Together they form a unique fingerprint.

Cite this