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
Neste artigo, consideramos o problema de incorporação de anel em gráficos estelares defeituosos. Nossa incorporação é baseada no esquema de transição de caminho e técnica de empréstimo de nó no anel de subestrelas quadridimensionais com falhas uniformemente distribuídas. Deixar Sn ser ngráfico estelar tridimensional tendo n! nós. Mostraremos que um anel de comprimento n! - 2f pode ser encontrada em Sn quando o número de nós defeituosos f é no máximo n-3. Na pior das hipóteses, a perda de 2f nós no tamanho de um anel livre de falhas é inevitável porque o gráfico estrela é bipartido. Além disso, este resultado é superior ao melhor resultado anterior que constrói o anel de comprimento n! - 4f sob a mesma condição de falha. Além disso, estendendo este resultado para o gráfico estrela com falhas de nó e de borda simultaneamente, podemos encontrar o anel de comprimento livre de falhas n! - 2 fn in Sn quando ele contém fn nós defeituosos e fe bordas defeituosas tais que fn + fe
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
Jung-Hwan CHANG, Chan-Su SHIN, Kyung-Yong CHWA, "Ring Embedding in Faulty Star Graphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E82-A, no. 9, pp. 1953-1964, September 1999, doi: .
Abstract: In this paper, we consider the ring embedding problem in faulty star graphs. Our embedding is based on the path transition scheme and node borrow technique in the ring of 4-dimensional substars with evenly distributed faults. Let Sn be the n-dimensional star graph having n! nodes. We will show that a ring of length n! - 2f can be found in Sn when the number of faulty nodes f is at most n-3. In the worst case, the loss of 2f nodes in the size of fault-free ring is inevitable because the star graph is bipartite. In addition, this result is superior to the best previous result that constructs the ring of length n! - 4f under the same fault condition. Moreover, by extending this result into the star graph with both node and edge faults simultaneously, we can find the fault-free ring of length n! - 2 fn in Sn when it contains fn faulty nodes and fe faulty edges such that fn + fe
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e82-a_9_1953/_p
Copiar
@ARTICLE{e82-a_9_1953,
author={Jung-Hwan CHANG, Chan-Su SHIN, Kyung-Yong CHWA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Ring Embedding in Faulty Star Graphs},
year={1999},
volume={E82-A},
number={9},
pages={1953-1964},
abstract={In this paper, we consider the ring embedding problem in faulty star graphs. Our embedding is based on the path transition scheme and node borrow technique in the ring of 4-dimensional substars with evenly distributed faults. Let Sn be the n-dimensional star graph having n! nodes. We will show that a ring of length n! - 2f can be found in Sn when the number of faulty nodes f is at most n-3. In the worst case, the loss of 2f nodes in the size of fault-free ring is inevitable because the star graph is bipartite. In addition, this result is superior to the best previous result that constructs the ring of length n! - 4f under the same fault condition. Moreover, by extending this result into the star graph with both node and edge faults simultaneously, we can find the fault-free ring of length n! - 2 fn in Sn when it contains fn faulty nodes and fe faulty edges such that fn + fe
keywords={},
doi={},
ISSN={},
month={September},}
Copiar
TY - JOUR
TI - Ring Embedding in Faulty Star Graphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1953
EP - 1964
AU - Jung-Hwan CHANG
AU - Chan-Su SHIN
AU - Kyung-Yong CHWA
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E82-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 1999
AB - In this paper, we consider the ring embedding problem in faulty star graphs. Our embedding is based on the path transition scheme and node borrow technique in the ring of 4-dimensional substars with evenly distributed faults. Let Sn be the n-dimensional star graph having n! nodes. We will show that a ring of length n! - 2f can be found in Sn when the number of faulty nodes f is at most n-3. In the worst case, the loss of 2f nodes in the size of fault-free ring is inevitable because the star graph is bipartite. In addition, this result is superior to the best previous result that constructs the ring of length n! - 4f under the same fault condition. Moreover, by extending this result into the star graph with both node and edge faults simultaneously, we can find the fault-free ring of length n! - 2 fn in Sn when it contains fn faulty nodes and fe faulty edges such that fn + fe
ER -