Date of Award


Document Type


Degree Name

Master of Science (MS)


Computer Science

Committee Chair

Peter J. Slater

Committee Member

Frank Zhu

Committee Member

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.



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.