A Naive Algorithm for Feedback Vertex Set

Author Yixin Cao



PDF
Thumbnail PDF

File

OASIcs.SOSA.2018.1.pdf
  • Filesize: 497 kB
  • 9 pages

Document Identifiers

Author Details

Yixin Cao

Cite AsGet BibTex

Yixin Cao. A Naive Algorithm for Feedback Vertex Set. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 1:1-1:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/OASIcs.SOSA.2018.1

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(c^k n^2) for some constant c.
Keywords
  • greedy algorithm
  • analysis of algorithms
  • branching algorithm
  • parameterized computation -- graph modification problem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail