EMBEDDING OF CYCLES IN ARRANGEMENT GRAPHS

被引：64

作者：

DAY, K ^{[1
]}

TRIPATHI, A ^{[1
]}

机构：

[1] UNIV MINNESOTA,DEPT COMP SCI,MINNEAPOLIS,MN 55455

来源：

IEEE TRANSACTIONS ON COMPUTERS | 1993年 / 42卷 / 08期

关键词：

ARRANGEMENT GRAPHS; DISJOINT CYCLES; EMBEDDINGS; HAMILTONIAN CYCLES; INTERCONNECTION NETWORKS; STAR GRAPHS;

D O I：

10.1109/12.238494

中图分类号：

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

学科分类号：

0812 ;

摘要：

Arrangement graphs have been recently proposed as an attractive interconnection topology for large multiprocessor systems. In this correspondence, we further study these graphs by first proving the existence of Hamiltonian cycles in any arrangement graph. Secondly, we prove that an arrangement graph contains cycles of all lengths ranging between 3 and the size of the graph. Finally, we show that an arrangement graph can be decomposed into node disjoint cycles in many different ways.

引用

页码：1002 / 1006

页数：5

共 7 条

[1]

Akers S. B., 1986, Proceedings of the 1986 International Conference on Parallel Processing (Cat. No.86CH2355-6), P216

[2]

Akers S. B., 1987, Proceedings of the 1987 International Conference on Parallel Processing, P393

[3]

BIGGS NL, 1979, 2ND INT C COMB MATH, V319, P71

[4]

DAY K, 1992, INFORMATION PROCESSI, P235

[5] A STUDY OF ODD GRAPHS AS FAULT-TOLERANT INTERCONNECTION NETWORKS [J].

GHAFOOR, A ;

BASHKOW, TR .

IEEE TRANSACTIONS ON COMPUTERS, 1991, 40 (02) :225-232

[6]

Jwo J.S., 1991, J CIRCUIT SYST COMP, V1, P43, DOI DOI 10.1142/S0218126691000215

[7]

QIU K, 1991, INFORM PROCESSING LE, P125

← 1 →