Date of Award
5-2007
Document Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Legacy Department
School of Computing
Committee Chair/Advisor
Hedetniemi, Stephen T
Abstract
The concept of alliances was introduced in 2002 in a paper by Kristiansen, Hedetniemi and Hedetniemi. Although research has been published on the mathematical properties of various types of alliances, until recently, no research has been done to develop algorithms or establish the complexity of decision problems for alliances in graphs.
This thesis presents the first algorithmic study of alliances in graphs. We present linear algorithms for finding various alliance numbers in trees and series parallel graphs. These linear algorithms are designed using a new methodology based on the well-established Wimer methodology for designing polynomial algorithms on k-terminal graphs. Linear algorithms on trees for minimum offensive, minimum powerful, minimum global defensive, minimum global offensive, and minimum global powerful alliances are presented. Also, a polynomial algorithm for finding the minimum defensive alliance number of a series parallel graph is presented. Additional linear algorithms are presented for minimum weighted defensive, minimum weighted offensive, minimum weighted powerful, minimum weighted global defensive, minimum weighted global offensive, and minimum weighted global powerful alliances.
We present the first complexity study of alliances in graphs. This study was developed concurrently with the work of Cami, Balakrishnan, Deo and Dutton. Complexity results for defensive, powerful, global defensive, and global powerful alliances when restricted to bipartite and chordal graphs are presented. Also, complexity results for weighted defensive, weighted offensive, weighted powerful, weighted global defensive, weighted global offensive, and weighted global powerful alliances when restricted to stars are presented.
In addition to interesting open questions, we also include implementations of the minimum powerful alliance algorithm on trees and the minimum weighted global defensive alliances on paths.
Recommended Citation
Jamieson, Lindsay, "Algorithms and Complexity for Alliances and Weighted Alliances of Various Types" (2007). All Dissertations. 66.
https://tigerprints.clemson.edu/all_dissertations/66