无向图中子集反馈顶点集问题的精确算法
作者：周晓清; 肖鸣宇
摘要：子集反馈顶点集问题是一个经典的NP难问题,该问题是指在一个无向图中删除最少的顶点使得图中某些给定的顶点不在任何圈中.子集反馈顶点集问题包含了经典的最小反馈顶点集、多路割等重要特例问题,并且可应用于电路测试、操作系统解死锁等领域.子集反馈顶点集问题也是精确算法中的一个重要问题,该问题存在一个运行时间为O~＊（2~n）的简单暴力搜索算法,其中n为图中顶点数.直到2011年Fomin等人给出一个运行时间为O~＊（1.8638n）的算法,这个运行时间界才被打破.文中将该运行时间上界进一步改进到O~＊（1.7743n）.文中的算法是一个分支搜索算法,为了改进该问题的运行时间界,文中对问题的结构性质进行了深入的分析,挖掘出若干有效的规约和分支规则,再采用测量治之方法对算法的运行时间进行分析,最终将运行时间上界给予改进.
分类：
- 期刊
- >
- 自然科学与工程技术
- >
- 信息科技
- >
- 电子信息科学综合
收录：
- 数学文摘
- 上海图书馆馆藏
- 维普收录(中)
- 知网收录(中)
- 万方收录(中)
- 剑桥科学文摘
- 北大期刊(中国人文社会科学期刊)
- 国家图书馆馆藏
- CSCD 中国科学引文数据库来源期刊(含扩展版)
- 文摘与引文数据库
- SA 科学文摘(英)
- JST 日本科学技术振兴机构数据库(日)
- EI 工程索引(美)
- 统计源期刊(中国科技论文优秀期刊)
关键词：
- np难问题
- 精确算法
- 测量治之
- 子集反馈顶点集问题
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
