TY - GEN
T1 - Algorithms for min-cut Linear arrangements of outerplanar graphs
AU - Chao, Liang Fang
AU - Sha, Edwin Hsing Mean
N1 - Publisher Copyright:
© 2012 IEEE.
PY - 1992
Y1 - 1992
N2 - A Linear Arrangement (LA) is an embedding of an outerplanar graph G in a row of nodes. The min-cut LA problem is to find an LA such that the cutwidth is minimized. This problem has many applications in VLSI designs. A linear-time approximation algorithm is presented to find an LA with cutwidth optimal within a constant factor. The Planar LA is an LA such that no two edges cross each other. Algorithms for this problem are also discussed. An abstraction, called dual tree, is used to design these algorithms.
AB - A Linear Arrangement (LA) is an embedding of an outerplanar graph G in a row of nodes. The min-cut LA problem is to find an LA such that the cutwidth is minimized. This problem has many applications in VLSI designs. A linear-time approximation algorithm is presented to find an LA with cutwidth optimal within a constant factor. The Planar LA is an LA such that no two edges cross each other. Algorithms for this problem are also discussed. An abstraction, called dual tree, is used to design these algorithms.
UR - https://www.scopus.com/pages/publications/85067253510
U2 - 10.1109/ISCAS.1992.230392
DO - 10.1109/ISCAS.1992.230392
M3 - 会议稿件
AN - SCOPUS:85067253510
T3 - Proceedings - IEEE International Symposium on Circuits and Systems
SP - 1851
EP - 1854
BT - 1992 IEEE International Symposium on Circuits and Systems, ISCAS 1992
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 1992 IEEE International Symposium on Circuits and Systems, ISCAS 1992
Y2 - 10 May 1992 through 13 May 1992
ER -