Please use this identifier to cite or link to this item:
Title: A naive algorithm for feedback vertex set
Authors: Cao, Y 
Keywords: Analysis of algorithms
Branching algorithm
Graph modification problem
Greedy algorithm
Parameterized computation
Issue Date: 2018
Publisher: Schloss Dagstuhl- Leibniz - Zentrum fur Informatik
Source: OpenAccess Series in Informatics, 2018, v. 61, 1 How to cite?
Journal: OpenAccess series in informatics 
Abstract: 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.
Description: 1st Symposium on Simplicity in Algorithms, SOSA 2018, New Orleans, United States, 7-10 Jan 2018
ISBN: 9.78396E+12
EISSN: 2190-6807
DOI: 10.4230/OASIcs.SOSA.2018.1
Appears in Collections:Conference Paper

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

Page view(s)

Citations as of Sep 18, 2018

Google ScholarTM



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