Approximability of the independent feedback vertex set problem for bipartite graphs
DOI10.1016/j.tcs.2020.10.026zbMath1471.68210OpenAlexW3095894106MaRDI QIDQ5919046
Takehiro Ito, Xiao Zhou, Yuma Tamura
Publication date: 15 December 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2020.10.026
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On parameterized independent feedback vertex set
- On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
- Some APX-completeness results for cubic graphs
- Independent feedback vertex sets for graphs of bounded diameter
- Independent feedback vertex set for \(P_5\)-free graphs
- Faster deterministic \textsc{Feedback Vertex Set}
- Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
- Partition the vertices of a graph into one independent set and one acyclic set
- On feedback vertex sets and nonseparating independent sets in cubic graphs
- Planar Formulae and Their Uses
- Approximation algorithms for NP-complete problems on planar graphs
- Improved Algorithms and Combinatorial Bounds for Independent Feedback Vertex Set
- A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
- Recognizing Graphs Close to Bipartite Graphs
- Approximability of the independent feedback vertex set problem for bipartite graphs
- An improved FPT algorithm for independent feedback vertex set
This page was built for publication: Approximability of the independent feedback vertex set problem for bipartite graphs
