TY - JOUR
T1 - Pancake graphs
T2 - Structural properties and conditional diagnosability
AU - Chang, Nai Wen
AU - Wu, Hsuan Jung
AU - Hsieh, Sun Yuan
N1 - Funding Information:
This work was supported in part by Ministry of Science and Technology under grant 109-2223-E-006-001-.
Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2022/12
Y1 - 2022/12
N2 - Because of the increasing size of multi-processor systems, processor-fault diagnosis has played critical role in measuring reliability. The diagnosability of numerous well-known multiprocessor systems has been widely investigated. The conditional diagnosability is a new measure of diagnosability by restricting an additional condition under which any fault set cannot contain all the neighbors of any node in a system. This study evaluated the conditional diagnosability for pancake graphs in the PMC model. First, several properties of pancake graphs were derived and, based on these properties, the conditional diagnosability of an n-dimensional pancake graph was shown to be 2 for n= 3 and 8 n- 21 for n≥ 4.
AB - Because of the increasing size of multi-processor systems, processor-fault diagnosis has played critical role in measuring reliability. The diagnosability of numerous well-known multiprocessor systems has been widely investigated. The conditional diagnosability is a new measure of diagnosability by restricting an additional condition under which any fault set cannot contain all the neighbors of any node in a system. This study evaluated the conditional diagnosability for pancake graphs in the PMC model. First, several properties of pancake graphs were derived and, based on these properties, the conditional diagnosability of an n-dimensional pancake graph was shown to be 2 for n= 3 and 8 n- 21 for n≥ 4.
UR - http://www.scopus.com/inward/record.url?scp=85134637124&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85134637124&partnerID=8YFLogxK
U2 - 10.1007/s10878-022-00877-8
DO - 10.1007/s10878-022-00877-8
M3 - Article
AN - SCOPUS:85134637124
SN - 1382-6905
VL - 44
SP - 3263
EP - 3293
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
IS - 5
ER -