Flipping Modules to Minimize Maximum Wire Length. Issue 1 (1995)

• Record Type: Journal Article
• Authors: Chong, Kyunrak; Sahni, Sartaj
• Is Part Of: VLSI design. Volume 3:Issue 1(1995)
• Page Start: 37
• Page End: 41
• Publication Date: 1995
• Subjects: Module flipping -- Maximum wire length -- Complexity; Integrated circuits -- Very large scale integration -- Periodicals; 621.395
• DOI: 10.1155/1995/69526
• Languages: English
• ISSNs: 1065-514X

Abstract

Abstract : We show that obtaining the optimal orientations of modules to minimize the length of the longest wire is NP-hard. If each module is permitted only two possible orientations, this can be done in linear time. When all four orientations are permissible and wires are restricted to connect modules whose separation is bounded by some constant, the problem also can be solved in linear time.