ISSN:
1572-9125
Schlagwort(e):
G.2.2
;
F.2.2
;
maximum weight independent set
;
dynamic programming
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Mathematik
Notizen:
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.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01934098
Permalink