TY - GEN
T1 - A naive algorithm for feedback vertex set
AU - Cao, Yixin
PY - 2018/1/1
Y1 - 2018/1/1
N2 - Given a graph on n vertices and an integer k, the feedback vertex set problem asks for the deletion of at most k vertices to make the graph acyclic. We show that a greedy branching algorithm, which always branches on an undecided vertex with the largest degree, runs in single-exponential time, i.e., O(ck· n2) for some constant c.
AB - Given a graph on n vertices and an integer k, the feedback vertex set problem asks for the deletion of at most k vertices to make the graph acyclic. We show that a greedy branching algorithm, which always branches on an undecided vertex with the largest degree, runs in single-exponential time, i.e., O(ck· n2) for some constant c.
KW - Analysis of algorithms
KW - Branching algorithm
KW - Graph modification problem
KW - Greedy algorithm
KW - Parameterized computation
UR - http://www.scopus.com/inward/record.url?scp=85040658600&partnerID=8YFLogxK
U2 - 10.4230/OASIcs.SOSA.2018.1
DO - 10.4230/OASIcs.SOSA.2018.1
M3 - Conference article published in proceeding or book
VL - 61
T3 - OpenAccess Series in Informatics
BT - 1st Symposium on Simplicity in Algorithms, SOSA 2018 - Co-located with the 29th ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
A2 - Seidel, Raimund
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 1st Symposium on Simplicity in Algorithms, SOSA 2018
Y2 - 7 January 2018 through 10 January 2018
ER -