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

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

7
Last Week
0
Last month
0
Citations as of Sep 10, 2017

WEB OF SCIENCETM
Citations

3
Last Week
0
Last month
0
Citations as of Sep 14, 2017

Page view(s)

36
Last Week
2
Last month
Checked on Sep 17, 2017

Google ScholarTM

Check

Altmetric



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