05834086

a

05834086 Harutyunyan, Ararat A fast algorithm for powerful alliances in trees. Wu, Weili (ed.) et al., Combinatorial optimization and applications. 4th international conference, COCOA 2010, Kailua-Kona, HI, USA, December 18--20, 2010. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-17457-5/pbk). Lecture Notes in Computer Science 6508, 31-40 (2010). 2010 Berlin: Springer EN alliances powerful alliances weighted trees algorithm

doi:10.1007/978-3-642-17458-2_4

Summary: 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$. Finding the smallest such set in general graphs is NP-complete, even when the weights are all the same. In this paper, we give a linear time algorithm that finds the smallest global powerful alliance of any weighted tree $T = (V,E)$.