Linear time algorithms for weighted offensive and powerful alliances in trees

摘要

Given a graph G = (V, E) with a positive weight function w on the vertices of G, a global powerful alliance of G is a subset S of V such that for every vertex v at least half of the total weight in the closed neighborhood of v is contributed by the vertices of S. A global offensive alliance is a subset S of V such that the above condition holds for every vertex v not in S. Finding the smallest such set in general graphs is NP-complete for both of these problems, even when the weights are all the same. In this paper, we give linear time algorithms that find the smallest global offensive and global powerful alliance of any weighted tree T = (V, E). (C) 2015 Elsevier B.V. All rights reserved.