Abstract
The maximum weight independent set problem for a general graph is NP-hard. But for some special classes of graphs, polynomial time algorithms do exist for solving it. Based on the divide-and-conquer strategy, Pawagi has presented an O(|V|log|V|) time algorithm for solving this problem on a tree. In this paper, we propose an O(|V|) time algorithm to improve Pawagi's result. The proposed algorithm is based on the dynamic programming strategy and is time optimal within a constant factor. © 1988 BIT Foundations.