EMBEDDING GRAPHS ONTO THE SUPERCUBE

被引：50

作者：

AULETTA, V

RESCIGNO, AA

SCARANO, V

机构：

[1] Dipartimento di Informatica ed Applicazioni, Universita di Salerno

[2] Department of Computer Science, University of Massachusetts, Amherst

来源：

IEEE TRANSACTIONS ON COMPUTERS | 1995年 / 44卷 / 04期

关键词：

CYCLES; GRAPH EMBEDDING; HAMILTONIAN CYCLE; PARALLEL ARCHITECTURES; SUPERCUBE;

D O I：

10.1109/12.376173

中图分类号：

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

学科分类号：

0812 ;

摘要：

In this paper we consider the Supercube, a new interconnection network derived from the Hypercube. The Supercube, introduced by sen in [10], has the same diameter and connectivity as a Hypercube but can be realized for any number of nodes, not only powers of 2. We study the Supercube's ability to execute parallel programs, using graph-embedding techniques. We show that complete binary trees and bidimensional meshes (with a side length power of 2) are spanning subgraphs of the Supercube. We then prove that the Supercube is Hamiltonian and, when the number of nodes is not a power of 2, it contains all cycles of length greater than 3 as subgraphs.

引用

页码：593 / 597

页数：5

共 13 条

[1]

Auletta V., 1993, Parallel Processing Letters, V3, P393, DOI 10.1142/S0129626493000435

[2]

AULETTA V, 1992, 4 P IT C THEOR COMP

[3]

Bhatt S., 1986, 27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), P274, DOI 10.1109/SFCS.1986.38

[4]

BHUYAN LN, 1984, IEEE T COMPUT, V33, P323, DOI 10.1109/TC.1984.1676437