Alliances are used to denote agreements between members of a group with similar interests. Alliances can occur between nations, biological sequences, business cartels, and other entities. The notion of alliances in graphs was first introduced by Kristiansen, Hedetniemi, and Hedetniemi in [KHH04]. A defensive alliance in a graph G = (V, E ) is a non empty set S ⊆ V where, for all x ∈ S, |N|[ x] ∩ S| ≥ |N|[x ] – S|. Consequently, every vertex that is a member of a defensive alliance has at least as many vertices defending it as there are vertices attacking it. Alliances in this sense can be used to model a variety of applications such as classification problems, communities in the World Wide Web, distributed protocols, etc [Sha01, FLG00, SX07]. In [GK98, GK00], Gerber and Kobler introduced the problem of partitioning a graph into strong defensive alliances for the first time as the “ Satisfactory Graph Partitioning (SGP)” problem. In his dissertation [Sha01], Shafique used the problem of partitioning a graph into alliances to model problems in data clustering.
Decision problems for several types of alliances and alliance partitions have been shown to be NP-complete. However, because of their applicability, it is of interest to study methods that overcome this complexity of these problems. In this thesis, we will present a variety of algorithms for finding alliances in different families of graphs, each with a running time that is polynomial in terms of the size of the input, where the exponential component is now in terms of an appropriate parameter rather than the input size. This study is guided by the theory of parameterized complexity introduced by Downey and Fellows in [DF99].
In addition to parameterized algorithms for alliance related problems, we study the partition of series-parallel graphs into alliances. The class of series-parallel graphs is a special class in graph theory since many problems known to be NP-complete on general graphs have been shown to have polynomial time algorithms on series-parallel graphs [ZLL04, Hoj95, DS99, HHL87, TNS82]. For example, the problem of finding a minimum defensive alliance has been shown to have a polynomial time algorithm when restricted to series-parallel graphs [Jam07]. Series-parallel graphs have also been the focus of study in a wide range of applications including CMOS layout and scheduling problems [ML86, Oud97]. Our motivation is driven by clustering properties that can be modeled with alliances. We observe that partitioning series-parallel graphs into alliances of roughly the same size can be used to partition task graphs to minimize the communication between processors and balance the workload of each processor. We present a characterization of series-parallel graphs that allow a partition into defensive alliances and a subclass of series-parallel graphs with a satisfactory partitions.
|Advisor:||Dutton, Ronald D.|
|School:||University of Central Florida|
|School Location:||United States -- Florida|
|Source:||DAI-B 71/04, Dissertation Abstracts International|
|Keywords:||Graph theory, Parameterized algorithms, Series-parallel graphs|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be