THE TWISTED N-CUBE WITH APPLICATION TO MULTIPROCESSING

被引：101

作者：

ESFAHANIAN, AH ^{[1
]}

NI, LM ^{[1
]}

SAGAN, BE ^{[1
]}

机构：

[1] MICHIGAN STATE UNIV,DEPT MATH,E LANSING,MI 48824

来源：

IEEE TRANSACTIONS ON COMPUTERS | 1991年 / 40卷 / 01期

关键词：

BINARY TREE; GRAPH THEORY; HYPERCUBE MULTIPROCESSORS; MESSAGE ROUTING; N-CUBE; PATTERN EMBEDDING; MEDIAN GRAPHS;

D O I：

10.1109/12.67323

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We show that by exchanging any two independent edges in any shortest cycle of the n-cube (n greater-than-or-equal-to 3), its diameter decreases by one unit. This leads us to define a new class of n-regular graphs, denoted TQ(n), with 2n vertices and diameter n - 1, which has the (n - 1)-cube as subgraph. Other properties of TQ(n) such as connectivity and the lengths of the disjoints paths are also investigated. Moreover, we show that the complete binary tree on 2n - 1 vertices, which is not a subgraph of the n-cube, is a subgraph of TQ(n). Finally, we discuss how these results can be used to enhance existing hypercube multiprocessors.

引用

页码：88 / 93

页数：6

共 29 条

[1]

ARMSTRONG JR, 1981, IEEE T COMPUT, V30, P587, DOI 10.1109/TC.1981.1675844

[2] INFINITE MEDIAN GRAPHS, (0,2)-GRAPHS, AND HYPERCUBES [J].

BANDELT, HJ ;

MULDER, HM .

JOURNAL OF GRAPH THEORY, 1983, 7 (04) :487-497

[3]

BHATT SN, 1985, YALEUDCSRR443 YAL U

[4]

BRANDENBURG JE, 1985, EMBEDDING SCOMMUNICA

[5]

CHAN TF, 1986, IEEE T COMPUT, V35, P969, DOI 10.1109/TC.1986.1676698

[6] PERFORMANCE ANALYSIS OF K-ARY N-CUBE INTERCONNECTION NETWORKS [J].

DALLY, WJ .

IEEE TRANSACTIONS ON COMPUTERS, 1990, 39 (06) :775-785

[7]

DEKEL E, 1983, IEEE T COMPUT, P307

[8]

Erdos P., 1979, Computers & Mathematics with Applications, V5, P33, DOI 10.1016/0898-1221(81)90137-1

[9]

ESFAHANIAN AH, IN PRESS IEEE T COMP

[10]

FATHI ET, 1983, COMPUTER, V16, P23, DOI 10.1109/MC.1983.1654324

← 1 2 3 →