带权无向图中反馈顶点集的固定参数枚举算法

王建新; 江国红; 陈建二

首页> 中文期刊> 《计算机学报》 >带权无向图中反馈顶点集的固定参数枚举算法

带权无向图中反馈顶点集的固定参数枚举算法

开具论文收录证明 >>

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

文献代查 >>

页面导航

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

摘要

反馈顶点集(FVS)问题是一个经典的NP-完全问题,在很多领域有重要的应用.人们对该问题进行了大量的研究,但目前还没有有效的算法枚举带权无向图的反馈顶点集.文中通过对带权无向图中反馈顶点集问题的结构的深入分析,给出了一个有效的基于分支搜索技术的固定参数枚举算法.算法将反馈顶点集问题转化为反馈边集问题,通过枚举z个权值最大的森林来枚举z个权值最小的含k条边的反馈边集,从而得到z个权值最小的含k个顶点的反馈顶点集,算法时间复杂度为O(5kn2(logn+k)+3kz(n2logn+z)).

著录项

来源
《计算机学报》 |2010年第7期|1140-1152|共13页
作者
王建新; 江国红; 陈建二;
展开▼
作者单位

中南大学信息科学与工程学院;

长沙;

410083;

中南大学信息科学与工程学院;

长沙;

410083;

中南大学信息科学与工程学院;

长沙;

410083;

展开▼
原文格式 PDF
正文语种 chi
中图分类理论、方法;
关键词
反馈顶点集; 无向图; 带权; 参数; 固定参数枚举;

相似文献

中文文献
外文文献
专利

1. 无向图中子集反馈顶点集问题的精确算法 [J] . 周晓清 ,肖鸣宇 . 计算机学报 . 2018,第003期
2. 权长相合的带权无向图画图算法 [J] . 张伟 ,曾瑞弼 ,胡明晓 . 计算机应用 . 2012,第004期
3. 一种基于带权无向图的中医方剂频繁项集挖掘算法 [J] . 谭龙 ,秦琦冰 . 计算机应用与软件 . 2017,第005期
4. 枚举一个无向图所有最小割集的一种简单算法 [J] . 乔文华 . 阴山学刊 . 1999,第005期
5. 带权最大割问题的一种基于划分技术的固定参数可解算法 [J] . 刘运龙 ,王建新 . 高技术通讯 . 2010,第003期
6. 搜索引擎中基于无向图的聚类算法研究 [C] . 李伟健 ,王实 ,刘湘草 . 第五届中国软件工程大会 . 2008
7. 面向复杂网络可控性的最小驱动点集枚举及优化选取算法研究 [A] . 王哲 . 2013

带权无向图中反馈顶点集的固定参数枚举算法

摘要

著录项

相似文献

相关主题

期刊订阅