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 -