ISSN:
1572-9125
Keywords:
G.2.2
;
F.2.2
;
maximum weight independent set
;
dynamic programming
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
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 anO(|V|log|V|) time algorithm for solving this problem on a tree. In this paper, we propose anO(|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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01934098
Permalink