An optimal time algorithm for finding a maximum weight independent set in a tree |
| |
| Authors: | G H Chen M T Kuo J P Sheu |
| |
| Institution: | (1) Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan, Republic of China;(2) Department of Electrical Engineering, National Central University, Chung-Li, Taiwan Republic of China |
| |
| 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. |
| |
| Keywords: | G 2 2 F 2 2 |
| 本文献已被 SpringerLink 等数据库收录！ |
|
