首页> 中文会议>第二届全国大学生创新论坛 >最小曼哈顿网络问题的近似算法及复杂性研究

最小曼哈顿网络问题的近似算法及复杂性研究

页面导航

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

摘要

时平面上的有限点集T以及由水平和垂直线段构成的网络G,若对T中任意两点p,q都有G长度为|p·x-q·x|+|p·y—q·y |的路径相连,则称G是T上的曼哈顿网络.满足这一条件的长度最短的网络称为最小曼哈顿网络.在本课题中,我们给出最小曼哈顿网络问题的两个2-近似算法,并证明了最小曼哈顿网络问题是强NP-完全的.

著录项

来源
《第二届全国大学生创新论坛》|2009年|347-349|共3页
会议地点南京
作者
郭泽宇;
展开▼
作者单位

教育部;

展开▼
会议组织
正文语种
原文格式 PDF
中图分类算法理论;
关键词
计算机科学; 最小曼哈顿网络; 近似算法; 计算复杂性;

相似文献

中文文献
外文文献
专利

1. 传感器网络中最小 k-连通 m-控制集问题的近似算法? [J] . 帅天平 ,李业芳 ,艾文宝 . 工程数学学报 . 2012,第005期
2. 传感器网络中最小k-连通m-控制集问题的近似算法 [J] . 帅天平 ,李业芳 ,艾文宝 . 工程数学学报 . 2012,第005期
3. 三维无线自组织网络中最小虚拟骨干的近似算法 [J] . 易梦 ,梁家荣 ,覃斌 . 计算机科学 . 2020,第007期
4. 无线传感器网络最小覆盖集的贪婪近似算法 [J] . 陆克中 ,孙宏元 . 软件学报 . 2010,第010期
5. 基于最小割集基础上的网络系统可靠性近似算法改进研究 [J] . 刘隆波 ,金家善 . 海军航空工程学院学报 . 2006,第001期
6. 基于最小最大遗憾的变速平行机鲁棒调度问题近似算法 [C] . XU Xiao-qing ,许晓晴 ,ZHANG Zong-ming . 第十九届中国管理科学学术年会 . -1
7. 基于冒泡排序的非曼哈顿通道布线问题中的串扰最小化研究 [A] . 于永斌 . 2004

最小曼哈顿网络问题的近似算法及复杂性研究

摘要

著录项

相似文献

相关主题

期刊订阅