Consider an undirected graph whose vertices are weighted. Finding an independent vertex set maximizing the sum of the weights is in general NP-hard. The problem remains NP-hard for planar graphs but is tractable in chordal graphs and in bipartite graphs.
This paper gives an algorithm for finding a maximum weight independent set in trees, in O(nlogn) steps. Briefly, the tree is split by removing its centroid. For each subtree so obtained, a maximum weight independent set is found, and these sets are then suitably merged to obtain a maximum weight independent set for the original tree. Since a tree is a bipartite graph, the bipartite algorithm could be applied instead, but doing so would raise the time bound to O(n2log n) steps.
