A Study for Conditional Diagnosability of Pancake Graphs

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)


Due to the increasing size of a multi-processor system, processor fault diagnosis has played an important role in measuring the reliability of the system. The diagnosability of many well-known multiprocessor systems has been widely investigated. The conditional diagnosability is a new measure of diagnosability by restricting an additional condition that any faulty set cannot contain all the neighbors of any node in a system. In this paper, we evaluate the conditional diagnosability for pancake graphs under the PMC model. We first derive several properties of pancake graphs, and then based on these properties, the conditional diagnosability of an n-dimensional pancake graph is shown to be 2 for n= 3 and 8 n- 21 for n≥ 4.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 27th International Conference, COCOON 2021, Proceedings
EditorsChi-Yeh Chen, Wing-Kai Hon, Ling-Ju Hung, Chia-Wei Lee
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages8
ISBN (Print)9783030895426
Publication statusPublished - 2021
Event27th International Conference on Computing and Combinatorics, COCOON 2021 - Tainan, Taiwan
Duration: 2021 Oct 242021 Oct 26

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13025 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference27th International Conference on Computing and Combinatorics, COCOON 2021

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'A Study for Conditional Diagnosability of Pancake Graphs'. Together they form a unique fingerprint.

Cite this