一类弱支配集问题的近似算法

幸冬梅

首页> 中文期刊> 《计算机工程与科学》 >一类弱支配集问题的近似算法

一类弱支配集问题的近似算法

开具论文收录证明 >>

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

文献代查 >>

页面导航

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

摘要

支配集问题和集合覆盖问题均是图论中的经典问题,尤其是集合覆盖问题,它的近似算法在许多其他问题中均有非常多的应用,如设施选址问题、服务器的安置问题等.本文研究了支配集问题和集合覆盖问题的关系,讨论了几个弱支配集问题和弱覆盖问题、弱集合覆盖问题等,给出完全支配集问题的近似比为1nn的近似算法,分析了弱完全支配集问题的不可近似比最小规模,讨论了集合击中问题和弱集合b-覆盖问题的最小规模,同时讨论了完全支配集问题、集合d-击中等问题的不可近似性.

著录项

来源
《计算机工程与科学》 |2008年第12期|97-101|共5页
作者
幸冬梅;
展开▼
作者单位

复旦大学计算机科学与工程系;

上海;

200433;

南昌大学数学系;

江西;

南昌;

330047;

展开▼
原文格式 PDF
正文语种 chi
中图分类算法理论;
关键词
支配集; 集合击中; 近似比; 近似算法;

相似文献

中文文献
外文文献
专利

1. 一类弱集合覆盖问题的近似算法 [J] . 张涌 ,朱洪 . 计算机学报 . 2005,第009期
2. 求一类上模集函数最小值问题的近似算法及性能保证 [J] . 张防防 ,王武民 ,柘晓莉 . 兰州交通大学学报 . 2008,第003期
3. 一种参考能量的最小连通支配集近似算法 [J] . 赵煜 ,降爱莲 . 传感器与微系统 . 2015,第001期
4. 两跳支配集的高效近似算法 [J] . 赵学锋 ,王占华 ,高红玉 . 西北师范大学学报（自然科学版） . 2011,第005期
5. 求解圆盘图中最小连通支配集的近似算法 [J] . 赵学锋 . 计算机应用 . 2011,第007期
6. 一类弱支配集问题的近似算法 [C] . . 2008年全国理论计算机科学学术年会 . 2008
7. 带测度函数的连通支配集问题及其近似算法 [A] . 马俊 . 2005

一类弱支配集问题的近似算法

摘要

著录项

相似文献

相关主题

期刊订阅