首页> 中文期刊> 《计算机科学》 >边带权最大独立集问题及其近似算法

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

开具论文收录证明 >>

期刊封面封底目录下载 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

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

著录项

来源
《计算机科学》 |2004年第9期|140-143|共4页
作者
张华; 朱洪;
展开▼
作者单位

复旦大学计算机工程系智能信息处理实验室;

上海;

200433;

复旦大学计算机工程系智能信息处理实验室;

上海;

200433;

展开▼
原文格式 PDF
正文语种 chi
中图分类人工智能理论;
关键词
带权最大独立集问题; 边带权最大独立集问题; NP-Complete; 近似算法;

相似文献

中文文献
外文文献
专利

1. 一种点边带权最小生成树的近似算法 [J] . 李镇坚 ,朱洪 . 计算机应用与软件 . 2008,第001期
2. 带权混合支配问题的近似算法研究 [J] . 张佳男 ,肖鸣宇 . 计算机科学 . 2018,第004期
3. 一种求解带权集合覆盖问题的近似算法 [J] . 张馨东 ,罗亮 . 温州大学学报（自然科学版） . 2008,第006期
4. 基于SINR模型构造负载均衡的带权生成树近似算法 [J] . 林玉梅 ,刘芳 ,孙晓敏 . 曲阜师范大学学报（自然科学版） . 2017,第002期
5. 带限制条件的多权最短路径近似算法 [J] . 戴树贵 ,孙强 ,潘荫荣 . 计算机工程 . 2003,第007期
6. 内点带权的最小生成树的近似算法 [C] . 王海涛 ,李建 ,葛启 . 2005年全国理论计算机科学学术年会 . 2005
7. 最小赋权连通集合覆盖问题的近似算法 [A] . 张育柏 . 2018

获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

客服微信
服务号