期刊导航
期刊开放获取
河南省图书馆
退出
期刊文献
+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
检索
高级检索
期刊导航
共找到
1
篇文章
<
1
>
每页显示
20
50
100
已选择
0
条
导出题录
引用分析
参考文献
引证文献
统计分析
检索结果
已选文献
显示方式:
文摘
详细
列表
相关度排序
被引量排序
时效性排序
顶点覆盖问题线性内核算法
被引量:
2
1
作者
蔡晟
Rudolf Fleischer
朱洪
《计算机研究与发展》
EI
CSCD
北大核心
2008年第z1期53-56,共4页
参数复杂性作为算法研究的一个重要分支近10年在国际上受到了广泛的关注,线性内核问题作为参数复杂性研究的一类重要问题被广泛研究.主要给出了顶点覆盖问题的线性内核算法,在国内首次从理论上证明了顶点覆盖问题存在线性内核.算法首先...
参数复杂性作为算法研究的一个重要分支近10年在国际上受到了广泛的关注,线性内核问题作为参数复杂性研究的一类重要问题被广泛研究.主要给出了顶点覆盖问题的线性内核算法,在国内首次从理论上证明了顶点覆盖问题存在线性内核.算法首先通过顶点覆盖问题的2近似算法,将图的顶点集合分成两个顶点集合A,B,进而通过一系列规约将原始图的顶点覆盖问题转换到新图的顶点覆盖问题,然后证明了新图的顶点数目至多为2k,并且2k是这个问题的下界(k为参数具体定义见文章).
展开更多
关键词
参数复杂性
内核
化
线性内核
定点覆盖
下载PDF
职称材料
题名
顶点覆盖问题线性内核算法
被引量:
2
1
作者
蔡晟
Rudolf Fleischer
朱洪
机构
复旦大学信息工程学院计算机系
华东师范大学软件学院
出处
《计算机研究与发展》
EI
CSCD
北大核心
2008年第z1期53-56,共4页
基金
上海重点学科建设基金项目(B412)
国家自然科学基金项目(60496321,60703091)
文摘
参数复杂性作为算法研究的一个重要分支近10年在国际上受到了广泛的关注,线性内核问题作为参数复杂性研究的一类重要问题被广泛研究.主要给出了顶点覆盖问题的线性内核算法,在国内首次从理论上证明了顶点覆盖问题存在线性内核.算法首先通过顶点覆盖问题的2近似算法,将图的顶点集合分成两个顶点集合A,B,进而通过一系列规约将原始图的顶点覆盖问题转换到新图的顶点覆盖问题,然后证明了新图的顶点数目至多为2k,并且2k是这个问题的下界(k为参数具体定义见文章).
关键词
参数复杂性
内核
化
线性内核
定点覆盖
Keywords
parameterized complexity
kernelization
linear kernel
vertex cover
分类号
TP3 [自动化与计算机技术—计算机科学与技术]
下载PDF
职称材料
题名
作者
出处
发文年
被引量
操作
1
顶点覆盖问题线性内核算法
蔡晟
Rudolf Fleischer
朱洪
《计算机研究与发展》
EI
CSCD
北大核心
2008
2
下载PDF
职称材料
已选择
0
条
导出题录
引用分析
参考文献
引证文献
统计分析
检索结果
已选文献
上一页
1
下一页
到第
页
确定
用户登录
登录
IP登录
使用帮助
返回顶部