Date of Award
Master of Science (MS)
Peter J. Slater
Mary Ellen Weisskopf
Self-stabilization (Computer science), Computer algorithms., Graph theory.
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.
Kunin, Alexander Boris, "Self-stabilizing algorithms for independence, domination, and coloring" (2012). Theses. 20.