A WELL-BEHAVED ENUMERATION OF STAR GRAPHS

被引：14

作者：

BAGHERZADEH, N ^{[1
]}

DOWD, M ^{[1
]}

LATIFI, S ^{[1
]}

机构：

[1] UNIV NEVADA,LAS VEGAS,NV 89154

来源：

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS | 1995年 / 6卷 / 05期

关键词：

INTERCONNECTION NETWORK; STAR GRAPH; INCOMPLETE STAR GRAPH; INTERVAL BROADCAST; HAMILTONIAN CYCLES;

D O I：

10.1109/71.382321

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

An enumeration of star graphs is given which has many useful properties. For example an arbitrary prefix or suffix is connected; indeed the diameter is O(n). As a consequence, there is an O(n) interval broadcast algorithm. Prefixes which have t(n - 1)! vertices for some t are especially well-behaved. The topology of, embeddings in, and algorithms for these graphs are considered, making use of the enumeration.

引用

页码：531 / 535

页数：5

共 16 条

[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]

ANNEXSTEIN F, 1990, ACM S PARALLEL ALGOR, P398

[4]

BAGHERZADEH N, 1994, ECE940201 U CAL DEP

[5]

DAY K, IN PRESS IEEE T PARA

[6]

FRAGOPOULOU P, 93346 QUEENS U DEP C

[7]

Garey M.R., 1979, COMPUTERS INTRACTABI, V174

[8]

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

[9] INCOMPLETE HYPERCUBES [J].

KATSEFF, HP .

IEEE TRANSACTIONS ON COMPUTERS, 1988, 37 (05) :604-608

[10]

KIM K, 1991, P 20 INT C PAR PROC, V3, P9

← 1 2 →