Toronto Metropolitan University
Dennis_Christopher.pdf (383.56 kB)

Error locating: degree constraints

Download (383.56 kB)
posted on 2021-05-24, 10:01 authored by Christopher Dennis
Error graphs are a useful mathematical tool for representing failing interactions in a system. This representation is used as the basis for constructing an error locating array (ELA). However, if too many errors are present in a given error graph, it may not be possible to locate all interactions. We say that a graph is locatable if an ELA can be built. Bounds on the total size of an error graph are known, bounds on the degree an error graph can have have not been considered. In this thesis we explore the maximum degree an error graph may have while still guaranteeing its locatability. We consider special cases for 3 and 4 partite error graphs as well as developing bounds on the degree of a general error graph. We describe a linear time algorithm which can be used to generate tests which have at most one failing interaction.





  • Master of Science


  • Applied Mathematics

Granting Institution

Ryerson University

LAC Thesis Type

  • Thesis

Usage metrics

    Applied Mathematics (Theses)