A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
From MaRDI portal
Recommendations
- Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs
- A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
- Approximating minimum feedback vertex sets in hypergraphs
- scientific article; zbMATH DE number 3876618
Cited in
(only showing first 100 items - show all)- Minimum feedback vertex sets in shuffle-based interconnection networks
- Resource allocation in bounded degree trees
- Feedback vertex sets in star graphs
- A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
- Flexible bandwidth assignment with application to optical networks
- On residual approximation in solution extension problems
- Kernels for deletion to classes of acyclic digraphs
- A faster parameterized algorithm for pseudoforest deletion
- Efficient algorithm for the vertex cover \(P_k\) problem on cacti
- Polynomial kernels for deletion to classes of acyclic digraphs
- An improved FPT algorithm for almost forest deletion problem
- The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
- New algorithms for maximum disjoint paths based on tree-likeness
- New bounds on the size of the minimum feedback vertex set in meshes and butterflies.
- A factor 2 approximation algorithm for the vertex cover P₃ problem
- Compact formulations and an iterated local search-based matheuristic for the minimum weighted feedback vertex set problem
- On the complexity of singly connected vertex deletion
- Polynomial time algorithms for tracking path problems
- On the feedback number of 3-uniform linear extremal hypergraphs
- Tracking paths
- Local search is a PTAS for feedback vertex set in minor-free graphs
- On the tractability of ( k , i )-coloring
- An approximation algorithm for the \(l\)-pseudoforest deletion problem
- Parameterised algorithms for deletion to classes of DAGs
- Fixed-parameter tractability for subset feedback set problems with parity constraints
- An improved exact algorithm for undirected feedback vertex set
- New upper bounds on feedback vertex numbers in butterflies
- On line graphs of subcubic triangle-free graphs
- Parameterized complexity of secluded connectivity problems
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
- Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
- The vertex cover \(P_3\) problem in cubic graphs
- Approximation algorithm for the minimum weight connected k-subgraph cover problem
- Admission control with advance reservations in simple networks
- Improved approximation for orienting mixed graphs
- Efficient approximation of convex recolorings
- Simultaneous feedback edge set: a parameterized perspective
- A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
- Towards a polynomial kernel for directed feedback vertex set
- Preprocessing to reduce the search space: antler structures for feedback vertex set
- Improved kernels for tracking paths
- Circumventing connectivity for kernelization
- Hitting forbidden minors: approximation and kernelization
- An Improved Exact Algorithm for Undirected Feedback Vertex Set
- Safe approximation and its relation to kernelization
- Deterministic Algorithms for the Independent Feedback Vertex Set Problem
- On Residual Approximation in Solution Extension Problems
- Approximation algorithms for orienting mixed graphs
- A quartic kernel for pathwidth-one vertex deletion
- Scattered packings of cycles
- Approximation algorithms for minimum chain vertex deletion
- Designing FPT algorithms for cut problems using randomized contractions
- A spin glass approach to the directed feedback vertex set problem
- A Linear Kernel for Planar Feedback Vertex Set
- Iterative Compression for Exactly Solving NP-Hard Minimization Problems
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Approximation algorithms for orienting mixed graphs
- Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
- Cycle bases in graphs characterization, algorithms, complexity, and applications
- Approximation and kernelization for chordal vertex deletion
- FPT algorithms for FVS parameterized by split and cluster vertex deletion sets and other parameters
- A fixed-parameter algorithm for the vertex cover P₃ problem
- The decycling number of generalized Petersen graphs
- Minimum feedback arc sets in rotator and incomplete rotator graphs
- Decycling bubble sort graphs
- On feedback vertex set: new measure and new structures
- Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
- On the Complexity of Singly Connected Vertex Deletion
- Hitting weighted even cycles in planar graphs
- An approximate kernel for connected feedback vertex set
- Decycling bipartite graphs
- scientific article; zbMATH DE number 7559376 (Why is no real title available?)
- Tight localizations of feedback sets
- Towards a polynomial kernel for directed feedback vertex set
- Achieving a global objective with competing networked agents in the framework of discrete event systems
- Tracking paths
- On making a distinguished vertex of minimum degree by vertex deletion
- Exact Algorithms for Maximum Acyclic Subgraph on a Superclass of Cubic Graphs
- scientific article; zbMATH DE number 970357 (Why is no real title available?)
- scientific article; zbMATH DE number 2230267 (Why is no real title available?)
- Tree deletion set has a polynomial kernel but no \(\mathrm{OPT}^\mathcal{O}(1)\) approximation)
- Erdős-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing
- Constant factor approximation for tracking paths and fault tolerant feedback vertex set
- Approximability of the independent feedback vertex set problem for bipartite graphs
- A polynomial sized kernel for tracking paths problem
- Constant factor approximation for tracking paths and fault tolerant feedback vertex set
- A polynomial kernel for 3-leaf power deletion
- MIP formulations for induced graph optimization problems: a tutorial
- Approximating power node-deletion problems
- scientific article; zbMATH DE number 7758338 (Why is no real title available?)
- Maximum weighted induced forests and trees: new formulations and a computational comparative review
- Minimization and parameterized variants of vertex partition problems on graphs
- Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes
- Spin Glass approach to the feedback vertex set problem
- Timeline cover in temporal graphs: exact and approximation algorithms
- Connected feedback vertex set on AT-free graphs
- Tradeoffs in process strategy games with application in the WDM reconfiguration problem
- Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs
- A primal-dual approximation algorithm for the vertex cover P^3 problem
- Preprocessing to reduce the search space: antler structures for feedback vertex set
This page was built for publication: A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4699157)
