Open AccessFlipping Modules to Minimize Maximum Wire Length
Author(s) -
Kyunrak Chong,
Sartaj Sahni
Publication year - 1994
Publication title -
vlsi design
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.123
H-Index - 24
eISSN - 1065-514X
pISSN - 1026-7123
DOI - 10.1155/1995/69526
Subject(s) - constant (computer programming) , bounded function , mathematics , algorithm , topology (electrical circuits) , computer science , mathematical analysis , combinatorics , programming language
We show that obtaining the optimal orientations of modules to minimize the length of the longest wire isNP-hard. If each module is permitted only two possible orientations, this can be done in linear time. When allfour orientations are permissible and wires are restricted to connect modules whose separation is bounded bysome constant, the problem also can be solved in linear time
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom