The Algorithmic Complexity Of Alliances In Graphs

摘要

In 2001 Kristiansen, Hedetniemi and Hedetniemi [9] first defined the concept of a defensive alliance in a graph, to be a subset S is contained in V of a graph G = (V, E) having the property that every vertex v ∈ S has at most one more neighbor in V-S than it has in S (i.e. |N[v] ∩ S| ≥ |N[v] - S|). Since then several other types of alliances have been defined and studied including strong, offensive, global, powerful, and secure alliances. To date, no algorithms or complexity analyses have been developed for alliances in graphs. This is the subject of this paper.