Date of Award
2012
Document Type
Thesis
Degree Name
Master of Science (MS)
Department
Computer Science
Committee Chair
Peter J. Slater
Committee Member
Frank Zhu
Committee Member
Mary Ellen Weisskopf
Subject(s)
Self-stabilization (Computer science), Computer algorithms, Graph theory
Abstract
Self-stabilization is an algorithmic design paradigm which, since its inception in the early 1970s, has been used to implement efficient solutions that arise in settings where nodes do not have complete knowledge of a network, and more abstractly, to find graph theoretic structures such as independent sets, dominating sets, and spanning trees. This thesis provides a historical overview of the field, as well as a survey of notable papers. In addition to this survey, we provide a simplification of a well-known spanning tree algorithm, and an extension, to provide a proper coloring of bipartite graphs. We also provide a comparison of known independence and domination algorithms based on the size of their output, providing a means of comparing the relative quality of these algorithms.
Recommended Citation
Kunin, Alexander Boris, "Self-stabilizing algorithms for independence, domination, and coloring" (2012). Theses. 20.
https://louis.uah.edu/uah-theses/20