Date of Award
8-2007
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Legacy Department
Computer Science
Committee Chair/Advisor
Hedetniemi, Stephen T
Committee Member
Goddard , Wayne
Committee Member
Dean , Brian
Committee Member
Grossman , Harold
Abstract
There is a dearth of algorithms that deal with edge-based problems in trees, specifically algorithms for edge sets that satisfy a particular parameter. The goal of this thesis is to create a methodology for designing algorithms for these edge-based problems. We will present a variant of the Wimer method [Wimer et al. 1985] [Wimer 1987] that can handle edge properties. We call this variant the Wimer edge variant. The thesis is divided into three sections, the first being a chapter devoted to defining and discussing the Wimer edge variant in depth, showing how to develop an algorithm using this variant, and an example of this process, including a run of an algorithm developed using this method.
The second section involves algorithms developed using the Wimer edge variant. We will provide algorithms for a variety of edge parameters, including four different matching parameters (connected, disconnected, induced and 2-matching), three different domination parameters (edge, total edge and edge-vertex) and two covering parameters (edge cover and edge cover irredundance). Each of these algorithms are discussed in detail and run in linear time.
The third section involves an attempt to characterize the Wimer edge variant. We show how the variant can be applied to three classes of graphs: weighted trees, unicyclic graphs and generalized series-parallel graphs. For each of these classes, we detail what adaptations are required (if any) and design an algorithm, including showing a run on an example graph. The fourth chapter is devoted to a discussion of what qualities a parameter has to have in order to be likely to have a solution using the Wimer edge variant. Also in this chapter we discuss classes of graphs that can utilize the Wimer edge variant.
Other topics discussed in this thesis include a literature review, and a discussion of future work. There are plenty of options for future work on this topic, which hopefully this thesis can inspire. The intent of this thesis is to provide the foundation for future algorithms and other work in this area.
Recommended Citation
Jamieson, Alan, "Linear-Time Algorithms for Edge-Based Problems" (2007). All Dissertations. 101.
https://open.clemson.edu/all_dissertations/101