期刊
ALGORITHMICA
卷 73, 期 1, 页码 63-86出版社
SPRINGER
DOI: 10.1007/s00453-014-9904-6
关键词
Disjoint feedback vertex set; Parameterized computation; Kernlization; Measure and bound; Cubic graphs; Cographicmatroid; Matroid intersection problem
资金
- US National Science Foundation [CCF-0830455, CCF-0917288]
- European Research Council (ERC) [280152]
- Hungarian Scientific Research Fund (OTKA) [NK105645]
We present a new parameterized algorithm for the feedback vertex set problem (fvs) on undirected graphs. We approach the problem by considering a variation of it, the disjoint feedback vertex set problem (disjoint-fvs), which finds a feedback vertex set of size that has no overlap with a given feedback vertex set of the graph . We develop an improved kernelization algorithm for disjoint-fvs and show that disjoint-fvs can be solved in polynomial time when all vertices in have degrees upper bounded by three. We then propose a new branch-and-search process on disjoint-fvs, and introduce a new branch-and-search measure. The process effectively reduces a given graph to a graph on which disjoint-fvs becomes polynomial-time solvable, and the new measure more accurately evaluates the efficiency of the process. These algorithmic and combinatorial studies enable us to develop an -time parameterized algorithm for the general fvs problem, improving all previous algorithms for the problem.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据