Permutation Layout with Limited Between-Pins Congestion

Sang-hyun CHOE, Toshinobu KASHIWABARA, Toshio FUJISAWA

Summary :

In this paper is given a necessary and sufficient condition for a permutation layout problem to have a wiring pattern such that no wire passes the upper area of the upper horizontal line, no wire intersects the lower horizontal line more than once, and between-pins congestion is not more than k, where the portion of the lower horizontal line which is placed to the left (resp., right) of the leftmost (resp., rightmost) terminal is considered to be a between-pins spacing. A linear time algorithm is given for the case k1, based on a graph theoretical representation of the condition.

• Publication: IEICE TRANSACTIONS on transactions Vol.E72-E No.12 pp.1425-1431
• Publication Date: 1989/12/25
• Type of Manuscript: PAPER
• Category: Algorithm, Data Structure and Computational Complexity

Authors

Sang-hyun CHOE
Toshinobu KASHIWABARA
Toshio FUJISAWA

Keyword