| 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 &sube V where, for all x &isin S, |N|[ x] &cap S| &ge |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. |
