Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
A Fast Algorithm for Powerful Alliances in Trees
verfasst von : Ararat Harutyunyan
Erschienen in: Combinatorial Optimization and Applications
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
).