Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/77440
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
URI: http://hdl.handle.net/10397/77440
ISBN: 9.78396E+12
EISSN: 2190-6807
DOI: 10.4230/OASIcs.SOSA.2018.1
Appears in Collections:Conference Paper

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

Page view(s)

1
Citations as of Sep 18, 2018

Google ScholarTM

Check

Altmetric


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