ON VLSI LAYOUTS OF THE STAR GRAPH AND RELATED NETWORKS

被引：19
作者：
SYKORA, O
VRTO, I
机构：
[1] Institute for Informatics, Slovak Academy of Sciences, 84235 Bratislava
来源：
INTEGRATION-THE VLSI JOURNAL | 1994年 / 17卷 / 01期
关键词：
AREA; ARRANGEMENT GRAPH; CONGESTION; CROSSING NUMBER; EMBEDDING; LAYOUT; PANCAKE GRAPH; STAR GRAPH;
D O I：
10.1016/0167-9260(94)90021-3
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
We prove that the minimal VLSI layout of the arrangement graph A(n, k) occupies Theta(n!/(n - k - 1)!)(2) area. As a special case we obtain an optimal layout for the star graph S-n with the area Theta(n!)(2). This answers an open problem posed by Akers et al. (1987). The method is also applied to the pancake graph. The results provide optimal upper and lower bounds for crossing numbers of the above graphs.
引用
收藏
页码：83 / 93
页数：11
相关论文
共 23 条
[1]  
Akers S. B., 1987, Proceedings of the 1987 International Conference on Parallel Processing, P393
[2]   A GROUP-THEORETIC MODEL FOR SYMMETRIC INTERCONNECTION NETWORKS [J].
AKERS, SB ;
KRISHNAMURTHY, B .
IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (04) :555-566
[3]  
AKL SB, 1991, P INT C PAR PROC 3, P100
[4]  
AKL SG, 1992, LECT NOTES COMPUT SC, V634, P565
[5]  
BREBNER G, 1985, P VLSI ALGORITHMS AR
[6]   ARRANGEMENT GRAPHS - A CLASS OF GENERALIZED STAR GRAPHS [J].
DAY, K ;
TRIPATHI, A .
INFORMATION PROCESSING LETTERS, 1992, 42 (05) :235-241
[7]  
DHALL SK, 1990, 2ND P IEEE S PAR DIS, P540
[8]  
ERDOS P, 1973, AM MATH MONTHLY, V80, P52, DOI DOI 10.2307/2319261
[9]   BOUNDS FOR SORTING BY PREFIX REVERSAL [J].
GATES, WH ;
PAPADIMITRIOU, CH .
DISCRETE MATHEMATICS, 1979, 27 (01) :47-57
[10]  
Gazit H., 1990, P ALGORITHMS INT S S, P338
123