Embedding paths of different lengths into crossed cubes

Jianxi Fan; Xiaola Lin; Xiaohua Jia

doi:10.1109/PDCAT.2005.132

Embedding paths of different lengths into crossed cubes

Jianxi Fan, Xiaola Lin, Xiaohua Jia

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

Abstract

Crossed cubes are attractive alternatives to the popular hypercubes with many advantageous properties. In this paper, we study embeddings of paths of different lengths between any two distinct nodes in crossed cubes. We prove two important results: (a) Paths of all possible lengths greater than or equal to the distance between any two nodes plus 2 can be embedded between the two nodes with dilation 1; And (b) in the n-dimensional crossed cube, for any two integers n ≥ 3 and l with 1 ≤ l ≤ [n+1/2] - 1, there always exist two nodes x and y, such that the distance between x and y is l and any path of length l + 1 cannot be embedded between x and y with dilation 1. The results improve those provided by Fan, Lin, and Jia. © 2005 IEEE.

Original language	English
Title of host publication	Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings
Pages	1008-1012
Volume	2005
DOIs	https://doi.org/10.1109/PDCAT.2005.132
Publication status	Published - 2005
Event	6th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2005 - Dalian, China Duration: 5 Dec 2005 → 8 Dec 2005

Publication series

Name
Volume	2005

Conference

Conference	6th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2005
Place	China
City	Dalian
Period	5/12/05 → 8/12/05

Research Keywords

Crossed cube
Graph embedding
Interconnection network
Parallel computing system

Access Output

10.1109/PDCAT.2005.132

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{7d253a1405ad4e4287dc753cc5c8713e,

title = "Embedding paths of different lengths into crossed cubes",

abstract = "Crossed cubes are attractive alternatives to the popular hypercubes with many advantageous properties. In this paper, we study embeddings of paths of different lengths between any two distinct nodes in crossed cubes. We prove two important results: (a) Paths of all possible lengths greater than or equal to the distance between any two nodes plus 2 can be embedded between the two nodes with dilation 1; And (b) in the n-dimensional crossed cube, for any two integers n ≥ 3 and l with 1 ≤ l ≤ [n+1/2] - 1, there always exist two nodes x and y, such that the distance between x and y is l and any path of length l + 1 cannot be embedded between x and y with dilation 1. The results improve those provided by Fan, Lin, and Jia. {\textcopyright} 2005 IEEE.",

keywords = "Crossed cube, Graph embedding, Interconnection network, Parallel computing system",

author = "Jianxi Fan and Xiaola Lin and Xiaohua Jia",

year = "2005",

doi = "10.1109/PDCAT.2005.132",

language = "English",

isbn = "0769524052",

volume = "2005",

pages = "1008--1012",

booktitle = "Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings",

note = "6th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2005 ; Conference date: 05-12-2005 Through 08-12-2005",

}

Fan, J, Lin, X & Jia, X 2005, Embedding paths of different lengths into crossed cubes. in Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings. vol. 2005, 1579084, pp. 1008-1012, 6th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2005, Dalian, China, 5/12/05. https://doi.org/10.1109/PDCAT.2005.132

Embedding paths of different lengths into crossed cubes. / Fan, Jianxi; Lin, Xiaola; Jia, Xiaohua.
Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings. Vol. 2005 2005. p. 1008-1012 1579084.

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Embedding paths of different lengths into crossed cubes

AU - Fan, Jianxi

AU - Lin, Xiaola

AU - Jia, Xiaohua

PY - 2005

Y1 - 2005

N2 - Crossed cubes are attractive alternatives to the popular hypercubes with many advantageous properties. In this paper, we study embeddings of paths of different lengths between any two distinct nodes in crossed cubes. We prove two important results: (a) Paths of all possible lengths greater than or equal to the distance between any two nodes plus 2 can be embedded between the two nodes with dilation 1; And (b) in the n-dimensional crossed cube, for any two integers n ≥ 3 and l with 1 ≤ l ≤ [n+1/2] - 1, there always exist two nodes x and y, such that the distance between x and y is l and any path of length l + 1 cannot be embedded between x and y with dilation 1. The results improve those provided by Fan, Lin, and Jia. © 2005 IEEE.

AB - Crossed cubes are attractive alternatives to the popular hypercubes with many advantageous properties. In this paper, we study embeddings of paths of different lengths between any two distinct nodes in crossed cubes. We prove two important results: (a) Paths of all possible lengths greater than or equal to the distance between any two nodes plus 2 can be embedded between the two nodes with dilation 1; And (b) in the n-dimensional crossed cube, for any two integers n ≥ 3 and l with 1 ≤ l ≤ [n+1/2] - 1, there always exist two nodes x and y, such that the distance between x and y is l and any path of length l + 1 cannot be embedded between x and y with dilation 1. The results improve those provided by Fan, Lin, and Jia. © 2005 IEEE.

KW - Crossed cube

KW - Graph embedding

KW - Interconnection network

KW - Parallel computing system

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-33745155038&origin=recordpage

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

U2 - 10.1109/PDCAT.2005.132

DO - 10.1109/PDCAT.2005.132

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 0769524052

SN - 9780769524054

VL - 2005

SP - 1008

EP - 1012

BT - Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings

T2 - 6th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2005

Y2 - 5 December 2005 through 8 December 2005

ER -

Embedding paths of different lengths into crossed cubes

Abstract

Publication series

Conference

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this