边带权最大独立集问题及其近似算法  

Edge Weighted Maximum Independent Set Problem and an Approximate Algorithm for it

作　　者：张华[1] 朱洪[1] 

机构地区：[1]复旦大学计算机工程系智能信息处理实验室,上海200433

出　　处：《计算机科学》2004年第9期140-143,共4页Computer Science

基　　金：科技部基金(No.2001CCA03000);国家自然科学基金(No.60273045);上海科学技术发展基金(No.025115032)

摘　　要：区别于传统对带权最大独立集问题的研完,本文从新的角度首先提出了边带权最大独立集问题,给出了完整的定义,证明了它的NP-Complete难解性。并且通过对问题结构的研完,给出了一个近似度为1/「(Δ′+1)/3」的近似算法,Δ′为图中点的最大度数。Different from traditional research domain of Weighted Maximum Independent set Problem, in this paper, we firstly propose Edge Weighted Maximum Independent set Problem,give the formal definition and prove it is Np-Complete. Through researching the structure of problem,we give an approximate algorithm to solve it, which has the approximation ratio 1/[△′+1]/3], where △′ is the maximum degree of the vertex in graph G.

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] O157[自动化与计算机技术—控制科学与工程]