Improved algorithms for feedback vertex set problems

2008/06/01 by Jianer Chen, Fedor V. Fomin, Yang Liu +2 · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Algorithm #Chordal graph #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Constraint Satisfaction and Optimization #Feedback arc set #Feedback vertex set #Graph #Independent set #Mathematics #Maximal independent set #Neighbourhood (mathematics) #Parameterized complexity #Set (abstract data type) #Vertex (graph theory) #Vertex cover

paper · pdf · doi:10.1016/j.jcss.2008.05.002

openalex publication_date 2008/06/01 · crossref created 2008/06/01 · crossref issued 2008/11/01 · crossref published 2008/11/01 · crossref published-print 2008/11/01 · crossref deposited 2019/05/11 · openalex created_date 2025/10/10 · crossref indexed 2026/05/13 · openalex updated_date 2026/07/31

Citations

• A fixed-parameter algorithm for the directed feedback vertex set problem
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Finding odd cycle transversals
• Randomized Algorithms for the Loop Cutset Problem
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization

Cited by

• Feedback vertex set [wikipedia]