Permutation Layout with Limited Between-Pins Congestion

Sang-hyun CHOE; Toshinobu KASHIWABARA; Toshio FUJISAWA

Permutation Layout with Limited Between-Pins Congestion

Sang-hyun CHOE, Toshinobu KASHIWABARA, Toshio FUJISAWA

Full Text Views

0

Share
Cite this

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

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Algorithm, Data Structure and Computational Complexity

Authors

Sang-hyun CHOE
Toshinobu KASHIWABARA
Toshio FUJISAWA

Keyword

Cite this

Copy

Sang-hyun CHOE, Toshinobu KASHIWABARA, Toshio FUJISAWA, "Permutation Layout with Limited Between-Pins Congestion" in IEICE TRANSACTIONS on transactions, vol. E72-E, no. 12, pp. 1425-1431, December 1989, doi: .
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/transactions/10.1587/e72-e_12_1425/_p

Copy

@ARTICLE{e72-e_12_1425,
author={Sang-hyun CHOE, Toshinobu KASHIWABARA, Toshio FUJISAWA, },
journal={IEICE TRANSACTIONS on transactions},
title={Permutation Layout with Limited Between-Pins Congestion},
year={1989},
volume={E72-E},
number={12},
pages={1425-1431},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={December},}

Copy

TY - JOUR
TI - Permutation Layout with Limited Between-Pins Congestion
T2 - IEICE TRANSACTIONS on transactions
SP - 1425
EP - 1431
AU - Sang-hyun CHOE
AU - Toshinobu KASHIWABARA
AU - Toshio FUJISAWA
PY - 1989
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E72-E
IS - 12
JA - IEICE TRANSACTIONS on transactions
Y1 - December 1989
AB - 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.
ER -