Realization of an arbitrary permutation on a hypercube

Xiaojun Shen; Qing Hu; Weifa Liang

doi:10.1016/0020-0190(94)90002-7

Realization of an arbitrary permutation on a hypercube

Xiaojun Shen
, Qing Hu
, Weifa Liang

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

10 Citations (Scopus)

Abstract

We present an explicit combinatorial algorithm for constructing a 2-realization for any given permutation on a circuit-switched d-dimensional hypercube (d-cube) such that the total number of directed edges used in the realization (counting every repetition) is bounded by d2^d, the total number of directed edges in the d-cube. As a corollary, this result implies a (2d-3) step realization on a packet-switched d-cube (d≥3). © 1994.

Original language	English
Pages (from-to)	237-243
Journal	Information Processing Letters
Volume	51
Issue number	5
DOIs	https://doi.org/10.1016/0020-0190(94)90002-7
Publication status	Published - 12 Sept 1994
Externally published	Yes

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Research Keywords

Algorithms
Circuit-switched network
Computer architecture
Hypercube
Interconnection network
Permutation capability

Access Output

10.1016/0020-0190(94)90002-7

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{ed6cd4bc4837411abcc0203a92cc85f8,

title = "Realization of an arbitrary permutation on a hypercube",

abstract = "We present an explicit combinatorial algorithm for constructing a 2-realization for any given permutation on a circuit-switched d-dimensional hypercube (d-cube) such that the total number of directed edges used in the realization (counting every repetition) is bounded by d2d, the total number of directed edges in the d-cube. As a corollary, this result implies a (2d-3) step realization on a packet-switched d-cube (d≥3). {\textcopyright} 1994.",

keywords = "Algorithms, Circuit-switched network, Computer architecture, Hypercube, Interconnection network, Permutation capability",

author = "Xiaojun Shen and Qing Hu and Weifa Liang",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].",

year = "1994",

month = sep,

day = "12",

doi = "10.1016/0020-0190(94)90002-7",

language = "English",

volume = "51",

pages = "237--243",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - Realization of an arbitrary permutation on a hypercube

AU - Shen, Xiaojun

AU - Hu, Qing

AU - Liang, Weifa

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 1994/9/12

Y1 - 1994/9/12

N2 - We present an explicit combinatorial algorithm for constructing a 2-realization for any given permutation on a circuit-switched d-dimensional hypercube (d-cube) such that the total number of directed edges used in the realization (counting every repetition) is bounded by d2d, the total number of directed edges in the d-cube. As a corollary, this result implies a (2d-3) step realization on a packet-switched d-cube (d≥3). © 1994.

AB - We present an explicit combinatorial algorithm for constructing a 2-realization for any given permutation on a circuit-switched d-dimensional hypercube (d-cube) such that the total number of directed edges used in the realization (counting every repetition) is bounded by d2d, the total number of directed edges in the d-cube. As a corollary, this result implies a (2d-3) step realization on a packet-switched d-cube (d≥3). © 1994.

KW - Algorithms

KW - Circuit-switched network

KW - Computer architecture

KW - Hypercube

KW - Interconnection network

KW - Permutation capability

UR - https://www.scopus.com/pages/publications/0028496437

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

U2 - 10.1016/0020-0190(94)90002-7

DO - 10.1016/0020-0190(94)90002-7

M3 - RGC 21 - Publication in refereed journal

SN - 0020-0190

VL - 51

SP - 237

EP - 243

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5

ER -

Realization of an arbitrary permutation on a hypercube

Abstract

Bibliographical note

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this