Pancake graphs: Structural properties and conditional diagnosability

Nai-Wen Chang (), Hsuan-Jung Wu () and Sun-Yuan Hsieh ()
Additional contact information
Nai-Wen Chang: National Cheng Kung University
Hsuan-Jung Wu: National Cheng Kung University
Sun-Yuan Hsieh: National Cheng Kung University

Journal of Combinatorial Optimization, 2022, vol. 44, issue 5, No 5, 3263-3293

Abstract: Abstract 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$$ n = 3 and $$8n-21$$ 8 n - 21 for $$n\ge 4$$ n ≥ 4 .

Keywords: Interconnection networks; PMC diagnosis model; Conditional diagnosability; Pancake graphs; Fault tolerance; Multiprocessor systems (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-022-00877-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:44:y:2022:i:5:d:10.1007_s10878-022-00877-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-022-00877-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().