Back to search

Clemson University

Algorithms and Complexity for Alliances and Weighted Alliances of Various Types

Abstract

dc:description.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.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy (PhD)
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
School of Computing

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Jamieson, Lindsay
Contributors dc:contributor
  • Hedetniemi, Stephen T

Subjects

dc:subject × 1

Identifiers

dc:identifier.*
Repository record dc:identifier
https://open.clemson.edu/all_dissertations/66

Chain of custody

source
Harvested from
Clemson University
Base URL
open.clemson.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Jamieson, Lindsay. Algorithms and Complexity for Alliances and Weighted Alliances of Various Types. Dissertation thesis, https://open.clemson.edu/all_dissertations/66