摘要： 区别于传统对带权最大独立集问题的研究，本文从新的角度首先提出了边带权最大独立集问题，给出了完整的定义，证明了它的NP-Complete难解性。并且通过对问题结构的研究，给出了一个近似度为1/[Δ′+1/3]的近似算法，Δ′为图中点的最大度数。

关键词: 最大独立集 近似算法 最大度 证明 中点 度数 NP 问题结构 区别 角度