The k-valent graph: A new family of cayley graphs for interconnection networks

Sun Yuan Hsieh; Tien Te Hsiao

doi:10.1109/ICPP.2004.1327923

The k-valent graph: A new family of cayley graphs for interconnection networks

Sun Yuan Hsieh, Tien Te Hsiao

Department of Computer Science and Information Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Citations (Scopus)

Abstract

This paper introduces a new family of Cayley graphs, named the k-valent graphs, for building interconnection networks. It includes the trivalent Cayley graphs (Vadapalli and Srimani, 1995) as a subclass. These new graphs are shown to be regular with the node-degree k, to have logarithmic diameter subject to the number of nodes, and to be k-connected as well as maximally fault tolerant. We also propose a shortest path routing algorithm and investigate some algebraic properties like cycles or cliques embedding.

Original language	English
Title of host publication	Proceedings - 2004 International Conference on Parallel Processing, ICPP 2004
Editors	R. Eigenmann
Pages	206-213
Number of pages	8
DOIs	https://doi.org/10.1109/ICPP.2004.1327923
Publication status	Published - 2004 Dec 17
Event	Proceedings - 2004 International Conference on Parallel Processing, ICPP 2004 - Montreal, Que, Canada Duration: 2004 Aug 15 → 2004 Aug 18

Publication series

Name	Proceedings of the International Conference on Parallel Processing
ISSN (Print)	0190-3918

Other

Other	Proceedings - 2004 International Conference on Parallel Processing, ICPP 2004
Country	Canada
City	Montreal, Que
Period	04-08-15 → 04-08-18

All Science Journal Classification (ASJC) codes

Hardware and Architecture
Engineering(all)

Access to Document

10.1109/ICPP.2004.1327923

Fingerprint Dive into the research topics of 'The k-valent graph: A new family of cayley graphs for interconnection networks'. Together they form a unique fingerprint.

Cite this

@inproceedings{1c3fcf9cfbdf4b8a81ec5c13dc5a0c86,

title = "The k-valent graph: A new family of cayley graphs for interconnection networks",

abstract = "This paper introduces a new family of Cayley graphs, named the k-valent graphs, for building interconnection networks. It includes the trivalent Cayley graphs (Vadapalli and Srimani, 1995) as a subclass. These new graphs are shown to be regular with the node-degree k, to have logarithmic diameter subject to the number of nodes, and to be k-connected as well as maximally fault tolerant. We also propose a shortest path routing algorithm and investigate some algebraic properties like cycles or cliques embedding.",

author = "Hsieh, {Sun Yuan} and Hsiao, {Tien Te}",

year = "2004",

month = dec,

day = "17",

doi = "10.1109/ICPP.2004.1327923",

language = "English",

isbn = "0769521975",

series = "Proceedings of the International Conference on Parallel Processing",

pages = "206--213",

editor = "R. Eigenmann",

booktitle = "Proceedings - 2004 International Conference on Parallel Processing, ICPP 2004",

note = "Proceedings - 2004 International Conference on Parallel Processing, ICPP 2004 ; Conference date: 15-08-2004 Through 18-08-2004",

}

Hsieh, SY & Hsiao, TT 2004, The k-valent graph: A new family of cayley graphs for interconnection networks. in R Eigenmann (ed.), Proceedings - 2004 International Conference on Parallel Processing, ICPP 2004. Proceedings of the International Conference on Parallel Processing, pp. 206-213, Proceedings - 2004 International Conference on Parallel Processing, ICPP 2004, Montreal, Que, Canada, 04-08-15. https://doi.org/10.1109/ICPP.2004.1327923

The k-valent graph : A new family of cayley graphs for interconnection networks. / Hsieh, Sun Yuan; Hsiao, Tien Te.

Proceedings - 2004 International Conference on Parallel Processing, ICPP 2004. ed. / R. Eigenmann. 2004. p. 206-213 (Proceedings of the International Conference on Parallel Processing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - The k-valent graph

T2 - Proceedings - 2004 International Conference on Parallel Processing, ICPP 2004

AU - Hsieh, Sun Yuan

AU - Hsiao, Tien Te

PY - 2004/12/17

Y1 - 2004/12/17

N2 - This paper introduces a new family of Cayley graphs, named the k-valent graphs, for building interconnection networks. It includes the trivalent Cayley graphs (Vadapalli and Srimani, 1995) as a subclass. These new graphs are shown to be regular with the node-degree k, to have logarithmic diameter subject to the number of nodes, and to be k-connected as well as maximally fault tolerant. We also propose a shortest path routing algorithm and investigate some algebraic properties like cycles or cliques embedding.

AB - This paper introduces a new family of Cayley graphs, named the k-valent graphs, for building interconnection networks. It includes the trivalent Cayley graphs (Vadapalli and Srimani, 1995) as a subclass. These new graphs are shown to be regular with the node-degree k, to have logarithmic diameter subject to the number of nodes, and to be k-connected as well as maximally fault tolerant. We also propose a shortest path routing algorithm and investigate some algebraic properties like cycles or cliques embedding.

UR - http://www.scopus.com/inward/record.url?scp=10044240513&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=10044240513&partnerID=8YFLogxK

U2 - 10.1109/ICPP.2004.1327923

DO - 10.1109/ICPP.2004.1327923

M3 - Conference contribution

AN - SCOPUS:10044240513

SN - 0769521975

T3 - Proceedings of the International Conference on Parallel Processing

SP - 206

EP - 213

BT - Proceedings - 2004 International Conference on Parallel Processing, ICPP 2004

A2 - Eigenmann, R.

Y2 - 15 August 2004 through 18 August 2004

ER -