The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Um conjunto de árvores geradoras de um gráfico G são chamadas de árvores geradoras completamente independentes (CISTs, para abreviar) se para cada par de vértices x, y∈V(G), os caminhos que se unem x e y em quaisquer duas árvores não têm vértice nem aresta em comum, exceto x e y. A construção de CISTs tem aplicações em redes de interconexão, como roteamento tolerante a falhas e transmissão segura de mensagens. Neste artigo, investigamos o problema de construção de dois CISTs no hipercubo balanceado BHn, que é uma rede variante do hipercubo e é superior ao hipercubo por ter um diâmetro menor. Como resultado, o diâmetro dos CISTs que construímos é igual a 9 para BH2 e 6n-2 para BHn quando n≥3.
Yi-Xian YANG
National Taipei University of Business
Kung-Jui PAI
Ming Chi University of Technology
Ruay-Shiung CHANG
National Taipei University of Business
Jou-Ming CHANG
National Taipei University of Business
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
Yi-Xian YANG, Kung-Jui PAI, Ruay-Shiung CHANG, Jou-Ming CHANG, "Constructing Two Completely Independent Spanning Trees in Balanced Hypercubes" in IEICE TRANSACTIONS on Information,
vol. E102-D, no. 12, pp. 2409-2412, December 2019, doi: 10.1587/transinf.2019PAL0001.
Abstract: A set of spanning trees of a graphs G are called completely independent spanning trees (CISTs for short) if for every pair of vertices x, y∈V(G), the paths joining x and y in any two trees have neither vertex nor edge in common, except x and y. Constructing CISTs has applications on interconnection networks such as fault-tolerant routing and secure message transmission. In this paper, we investigate the problem of constructing two CISTs in the balanced hypercube BHn, which is a hypercube-variant network and is superior to hypercube due to having a smaller diameter. As a result, the diameter of CISTs we constructed equals to 9 for BH2 and 6n-2 for BHn when n≥3.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2019PAL0001/_p
Copiar
@ARTICLE{e102-d_12_2409,
author={Yi-Xian YANG, Kung-Jui PAI, Ruay-Shiung CHANG, Jou-Ming CHANG, },
journal={IEICE TRANSACTIONS on Information},
title={Constructing Two Completely Independent Spanning Trees in Balanced Hypercubes},
year={2019},
volume={E102-D},
number={12},
pages={2409-2412},
abstract={A set of spanning trees of a graphs G are called completely independent spanning trees (CISTs for short) if for every pair of vertices x, y∈V(G), the paths joining x and y in any two trees have neither vertex nor edge in common, except x and y. Constructing CISTs has applications on interconnection networks such as fault-tolerant routing and secure message transmission. In this paper, we investigate the problem of constructing two CISTs in the balanced hypercube BHn, which is a hypercube-variant network and is superior to hypercube due to having a smaller diameter. As a result, the diameter of CISTs we constructed equals to 9 for BH2 and 6n-2 for BHn when n≥3.},
keywords={},
doi={10.1587/transinf.2019PAL0001},
ISSN={1745-1361},
month={December},}
Copiar
TY - JOUR
TI - Constructing Two Completely Independent Spanning Trees in Balanced Hypercubes
T2 - IEICE TRANSACTIONS on Information
SP - 2409
EP - 2412
AU - Yi-Xian YANG
AU - Kung-Jui PAI
AU - Ruay-Shiung CHANG
AU - Jou-Ming CHANG
PY - 2019
DO - 10.1587/transinf.2019PAL0001
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E102-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2019
AB - A set of spanning trees of a graphs G are called completely independent spanning trees (CISTs for short) if for every pair of vertices x, y∈V(G), the paths joining x and y in any two trees have neither vertex nor edge in common, except x and y. Constructing CISTs has applications on interconnection networks such as fault-tolerant routing and secure message transmission. In this paper, we investigate the problem of constructing two CISTs in the balanced hypercube BHn, which is a hypercube-variant network and is superior to hypercube due to having a smaller diameter. As a result, the diameter of CISTs we constructed equals to 9 for BH2 and 6n-2 for BHn when n≥3.
ER -