期刊文献+
任意字段
题名或关键词
题名
关键词
摘要
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
共找到2篇文章
< 1 >
每页显示 20 50 100
已选0条
引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
显示方式：
TWO FEEDBACK PROBLEMS FOR GRAPHS WITH BOUNDED TREE-WIDTH 认领 引用
1
作者 ZhangShaoqiang LiGuojun SohnMoo-Young 《Applied Mathematics(A Journal of Chinese Universities)》 2004年第2期149-154,共6页
Many difficult (often NP-complete) optimization problems can be solved efficiently on graphs of small tree-width with a given tree-decomposition.In this paper,it is discussed how to solve the minimum feedback vertex s... Many difficult (often NP-complete) optimization problems can be solved efficiently on graphs of small tree-width with a given tree-decomposition.In this paper,it is discussed how to solve the minimum feedback vertex set problem and the minimum vertex feedback edge set problem efficiently by using dynamic programming on a tree-decomposition. 展开更多
关键词 feedback vertex set feedback edge set,tree-decomposition,tree-width,dynamic programming.
暂未订购 下载PDF
Parameter Ecology for Feedback Vertex Set 认领 引用
2
作者 Bart M.P.Jansen Venkatesh Raman Martin Vatshelle 《Tsinghua Science and Technology》 SCIE EI CAS 2014年第4期387-409,共23页
This paper deals with the FEEDBACK VERTEX SET problem on undirected graphs, which asks for the existence of a vertex set of bounded size that intersects all cycles. Due it is theoretical and practical importance,the p... This paper deals with the FEEDBACK VERTEX SET problem on undirected graphs, which asks for the existence of a vertex set of bounded size that intersects all cycles. Due it is theoretical and practical importance,the problem has been the subject of intensive study. Motivated by the parameter ecology program we attempt to classify the parameterized and kernelization complexity of FEEDBACK VERTEX SET for a wide range of parameters.We survey known results and present several new complexity classifications. For example, we prove that FEEDBACK VERTEX SET is fixed-parameter tractable parameterized by the vertex-deletion distance to a chordal graph. We also prove that the problem admits a polynomial kernel when parameterized by the vertex-deletion distance to a pseudo forest, a graph in which every connected component has at most one cycle. In contrast, we prove that a slightly smaller parameterization does not allow for a polynomial kernel unless NP coNP=poly and the polynomial-time hierarchy collapses. 展开更多
关键词 feedback vertex set parameterized complexity parameter ecology program structural parameterizations kernelization
暂未订购 下载PDF
已选0条
引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
上一页 1 下一页 到第 页
在线咨询 使用帮助 返回顶部 意见反馈