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)- On the complexity of singly connected vertex deletion
- Feedback numbers of de Bruijn digraphs
- Minimization and parameterized variants of vertex partition problems on graphs
- Decycling bubble sort graphs
- On feedback vertex set: new measure and new structures
- Improved kernels for tracking paths
- Exact algorithms for the maximum k-balanced weighted biclique problem
- Nonpartisan feedback vertex set
- A faster parameterized algorithm for pseudoforest deletion
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- Smaller kernels for 3-leaf power modifications problems
- Exact Algorithms for Maximum Acyclic Subgraph on a Superclass of Cubic Graphs
- Circumventing connectivity for kernelization
- A constant-factor approximation for weighted bond cover
- Approximation algorithms for minimum chain vertex deletion
- scientific article; zbMATH DE number 2230267 (Why is no real title available?)
- A constant factor approximation for directed feedback vertex set in graphs of bounded genus
- Local search is a PTAS for feedback vertex set in minor-free graphs
- Approximate monotone local search for weighted problems
- Hitting forbidden minors: approximation and kernelization
- Characterizing the extremal k-girth graphs on feedback vertex set
- An approximate kernel for connected feedback vertex set
- On making a distinguished vertex of minimum degree by vertex deletion
- Exact and approximation algorithms for covering timeline in temporal graphs
- Achieving a global objective with competing networked agents in the framework of discrete event systems
- Parameterised algorithms for deletion to classes of DAGs
- scientific article; zbMATH DE number 970357 (Why is no real title available?)
- Timeline cover in temporal graphs: exact and approximation algorithms
- Improved approximation for orienting mixed graphs
- scientific article; zbMATH DE number 7559376 (Why is no real title available?)
- Tight localizations of feedback sets
- Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs
- Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
- A spin glass approach to the directed feedback vertex set problem
- A Linear Kernel for Planar Feedback Vertex Set
- Improved approximation algorithm for convex recoloring of trees
- A polynomial sized kernel for tracking paths problem
- Approximation algorithms for orienting mixed graphs
- Approximability of the independent feedback vertex set problem for bipartite graphs
- Designing FPT algorithms for cut problems using randomized contractions
- Approximation algorithms for orienting mixed graphs
- Cycle bases in graphs characterization, algorithms, complexity, and applications
- Iterative Compression for Exactly Solving NP-Hard Minimization Problems
- Using fractional primal-dual to schedule split intervals with demands
- A fixed-parameter algorithm for the vertex cover P₃ problem
- Towards a polynomial kernel for directed feedback vertex set
- Polynomial kernelizations for MIN \(F^{+}\Pi _{1}\) and MAX NP
- Towards a polynomial kernel for directed feedback vertex set
- Minimum feedback vertex sets in shuffle-based interconnection networks
- A primal-dual approximation algorithm for the vertex cover P^3 problem
- Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes
- An efficient approximation for the generalized assignment problem
- Efficient algorithm for the vertex cover \(P_k\) problem on cacti
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- A polynomial kernel for 3-leaf power deletion
- Improved algorithms for feedback vertex set problems
- Combination of parallel machine scheduling and vertex cover
- On the tractability of ( k , i )-coloring
- Wannabe bounded treewidth graphs admit a polynomial kernel for directed feedback vertex set
- Fixed-parameter tractability for subset feedback set problems with parity constraints
- Approximating power node-deletion problems
- Approximation and kernelization for chordal vertex deletion
- Approximating power node-deletion problems
- Hitting weighted even cycles in planar graphs
- New upper bounds on feedback vertex numbers in butterflies
- On residual approximation in solution extension problems
- scientific article; zbMATH DE number 7758338 (Why is no real title available?)
- A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
- An improved FPT algorithm for almost forest deletion problem
- Polynomial kernels for deletion to classes of acyclic digraphs
- On the Complexity of Singly Connected Vertex Deletion
- Admission control with advance reservations in simple networks
- A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
- Constant factor approximation for tracking paths and fault tolerant feedback vertex set
- New bounds on the size of the minimum feedback vertex set in meshes and butterflies.
- FPT algorithms for FVS parameterized by split and cluster vertex deletion sets and other parameters
- The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
- A quartic kernel for pathwidth-one vertex deletion
- On the minimum feedback vertex set problem: Exact and enumeration algorithms
- Feedback vertex set on AT-free graphs
- Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
- Scattered packings of cycles
- Tree deletion set has a polynomial kernel but no \(\mathrm{OPT}^\mathcal{O}(1)\) approximation)
- Tradeoffs in process strategy games with application in the WDM reconfiguration problem
- Polynomial time algorithms for tracking path problems
- Tracking paths
- Compact formulations and an iterated local search-based matheuristic for the minimum weighted feedback vertex set problem
- Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
- A factor 2 approximation algorithm for the vertex cover P₃ problem
- MIP formulations for induced graph optimization problems: a tutorial
- On the feedback number of 3-uniform linear extremal hypergraphs
- On line graphs of subcubic triangle-free graphs
- Preprocessing to reduce the search space: antler structures for feedback vertex set
- Deterministic Algorithms for the Independent Feedback Vertex Set Problem
- Flexible bandwidth assignment with application to optical networks
- Feedback vertex sets in star graphs
- Resource allocation in bounded degree trees
- Spin Glass approach to the feedback vertex set problem
- New algorithms for maximum disjoint paths based on tree-likeness
- Parameterized complexity of secluded connectivity problems
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)
