Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/20237
Title: | On Feedback Vertex Set: New Measure and New Structures | Authors: | Cao, Y Chen, J Liu, Y |
Keywords: | Cographic matroid Cubic graphs Disjoint feedback vertex set Kernlization Matroid intersection problem Measure and bound Parameterized computation |
Issue Date: | 2015 | Publisher: | Springer | Source: | Algorithmica, 2015, v. 73, no. 1, p. 63-86 How to cite? | Journal: | Algorithmica | Abstract: | 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 k that has no overlap with a given feedback vertex set F of the graph G. We develop an improved kernelization algorithm for disjoint-fvs and show that disjoint-fvs can be solved in polynomial time when all vertices in G\F 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 O∗(3.83k)-time parameterized algorithm for the general fvs problem, improving all previous algorithms for the problem. | URI: | http://hdl.handle.net/10397/20237 | ISSN: | 0178-4617 | EISSN: | 1432-0541 | DOI: | 10.1007/s00453-014-9904-6 |
Appears in Collections: | Journal/Magazine Article |
Show full item record
SCOPUSTM
Citations
13
Last Week
0
0
Last month
0
0
Citations as of Apr 23, 2018
WEB OF SCIENCETM
Citations
6
Last Week
1
1
Last month
0
0
Citations as of Mar 29, 2018
Page view(s)
51
Last Week
0
0
Last month
Citations as of Apr 22, 2018

Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.