Current Search: parameterized complexity (x)


Title

ALLIANCES IN GRAPHS: PARAMETERIZED ALGORITHMS ANDON PARTITIONING SERIESPARALLEL GRAPHS.

Creator

Enciso, Rosa, Dutton, Ronald, University of Central Florida

Abstract / Description

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 . A defensive alliance in a graph G=(V,E) is a non empty set S⊆V S where, for all x ∈S, N∩S≥NS. Consequently, every vertex that is a member of a defensive alliance has at least as...
Show moreAlliances 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 . A defensive alliance in a graph G=(V,E) is a non empty set S⊆V S where, for all x ∈S, N∩S≥NS. 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 can be used to model a variety of applications such as classification problems, communities in the web distributed protocols, etc . In , 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 , 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 NPcomplete. However, because of their applicability, it is of interest to study methods to overcome the complexity of these problems. In this thesis, we will present a variety of algorithms for finding alliances in different families of graphs with a running time that is polynomial in terms of the size of the input, and allowing exponential running time as a function of a chosen parameter. This study is guided by the theory of parameterized complexity introduced by Rod Downey and Michael Fellows in . In addition to parameterized algorithms for alliance related problems, we study the partition of seriesparallel graphs into alliances. The class of seriesparallel graphs is a special class in graph theory since many problems known to be NPcomplete on general graphs have been shown to have polynomial time algorithms on seriesparallel graphs. For example, the problem of finding a minimum defensive alliance has been shown to have a linear time algorithm when restricted to seriesparallel graphs . Seriesparallel graphs have also been to 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 seriesparallel 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 seriesparallel graphs that allow a partition into defensive alliances and a subclass of seriesparallel graphs with a satisfactory partitions.
Show less

Date Issued

2009

Identifier

CFE0002956, ucf:47945

Format

Document (PDF)

PURL

http://purl.flvc.org/ucf/fd/CFE0002956