A naive algorithm for feedback vertex set

DOI10.4230/OASIcs.SOSA.2018.1zbMath1433.68283arXiv1707.08684OpenAlexW2963205614MaRDI QIDQ5240414

Yixin Cao

Publication date: 25 October 2019

Full work available at URL: https://arxiv.org/abs/1707.08684

zbMATH Keywords

greedy algorithmanalysis of algorithmsparameterized computationgraph modification problembranching algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10)

Related Items (8)

A parameterized complexity view on collapsing \(k\)-cores ⋮ On the Complexity of Singly Connected Vertex Deletion ⋮ Approximating power node-deletion problems ⋮ Unnamed Item ⋮ Improved FPT Algorithms for Deletion to Forest-Like Structures. ⋮ Improved analysis of highest-degree branching for feedback vertex set ⋮ Unnamed Item ⋮ On the complexity of singly connected vertex deletion

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On feedback vertex set: new measure and new structures
• A note on approximation of the vertex cover and feedback vertex set problems -- Unified approach
• Network-based heuristics for constraint-satisfaction problems
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
• The node-deletion problem for hereditary properties is NP-complete
• A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Faster deterministic \textsc{Feedback Vertex Set}
• Nonconstructive tools for proving polynomial-time decidability
• A Sufficient Condition for Backtrack-Free Search
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions

This page was built for publication: A naive algorithm for feedback vertex set