论文摘要
很多树宽较小的NP难问题能用树分解技术在多项式时间内求解,寻找无向图的树宽有助于提高求解效率。因此,基于图的平均度提出了两种新的树分解启发式算法。这两种算法根据树分解与图三角化之间的关系,利用顶点度与平均度的偏差和填边数构造顶点消除序列,快速得到树分解的宽度。在随机正则图和DIMACS图着色实例上的测试结果表明:这两种算法简单易实现,与最小填边法相比能找到更优的树宽上界。
论文目录
文章来源
类型: 期刊论文
作者: 沈静,任耀峰,梅丹,杨美妮
关键词: 树宽,树分解,启发式算法
来源: 海军工程大学学报 2019年05期
年度: 2019
分类: 工程科技Ⅱ辑,基础科学,信息科技
专业: 数学,自动化技术
单位: 海军工程大学基础部
基金: 国家自然科学基金资助项目(61402516,61370052),海军工程大学自主立项资助项目(20160331)
分类号: TP18;O157.5
页码: 49-53
总页数: 5
文件大小: 187K
下载量: 26
相关论文文献
- [1].聚散优化算法:一种新的启发式算法[J]. 计算机集成制造系统 2020(03)
- [2].几种具有代表性的启发式算法研究[J]. 电子制作 2016(02)
- [3].共享单车再平衡问题及其容差插入启发式算法[J]. 运筹与管理 2019(10)
- [4].单体型装配问题的启发式算法研究[J]. 数字技术与应用 2017(01)
- [5].圆形件下料顺序分组启发式算法的设计与实现[J]. 图学学报 2017(01)
- [6].装备维修器材生产路径决策的两阶启发式算法[J]. 国防科技大学学报 2020(05)
- [7].基于一种特设启发式算法的车辆优化调度问题研究[J]. 电视技术 2019(04)
- [8].求解带硬时间窗车辆路径问题的时差插入启发式算法[J]. 计算机应用 2012(11)
- [9].求解柔性工件调度问题的启发式算法[J]. 科技风 2018(22)
- [10].基于超启发式算法的备件供应网络结构优化[J]. 系统工程与电子技术 2020(03)
- [11].基于启发式算法的自动化跨运车作业调度[J]. 上海大学学报(自然科学版) 2017(03)
- [12].三层物流网络选址—路径优化及混合启发式算法研究[J]. 计算机应用研究 2017(08)
- [13].基于混合顺序启发式算法的一维下料问题[J]. 中国机械工程 2014(16)
- [14].分配问题的启发式算法求解[J]. 甘肃联合大学学报(自然科学版) 2009(03)
- [15].一种有效求解厌恶设施选址问题的混合启发式算法[J]. 北京化工大学学报(自然科学版) 2017(06)
- [16].基于混合启发式算法的设备混合布局问题[J]. 工业工程 2017(01)
- [17].启发式算法的孔群加工路线模糊多目标优化[J]. 现代制造工程 2016(04)
- [18].多目标飞机和旅客恢复分阶段启发式算法[J]. 计算机应用研究 2014(08)
- [19].时变车辆路径问题的启发式算法[J]. 系统工程学报 2012(02)
- [20].阿德兰启发式算法在加油站选址中的应用[J]. 价值工程 2009(06)
- [21].混合启发式算法在汽车调度中的应用[J]. 电子技术应用 2009(07)
- [22].基于启发式算法的检测资源分配研究[J]. 锻压装备与制造技术 2018(02)
- [23].一种求解两级累计式车辆路径问题的两阶段启发式算法[J]. 机电一体化 2014(04)
- [24].模块度优化启发式算法应用[J]. 现代电子技术 2012(19)
- [25].基于阿德兰启发式算法的邮政网点选址研究[J]. 邮政研究 2011(05)
- [26].订货批量问题改进的相关策略启发式算法与仿真分析[J]. 系统仿真学报 2008(18)
- [27].基于元启发式算法的复杂车辆路径问题研究[J]. 物流技术 2013(21)
- [28].元启发式算法在校车路径规划中的应用[J]. 地理空间信息 2013(05)
- [29].无等待流水调度问题迭代启发式算法[J]. 安徽师范大学学报(自然科学版) 2009(01)
- [30].城市消防站点布局的改进启发式算法[J]. 数学的实践与认识 2008(01)