Pancake Graphs: Structural Properties and Conditional Diagnosability

  • 吳 宣融

Student thesis: Master's Thesis


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 In 2005 Lai et al proposed conditional diagnosability 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 pancake graphs is a great substitute to the hypercube in a parallel system We derives several properties of pancake graphs and then based on these properties the conditional diagnosability of an n-dimensional pancake graph is shown to be 8n - 21 for n >= 5
Date of Award2014 Aug 25
Original languageEnglish
SupervisorSun-Yuan Hsieh (Supervisor)

Cite this