Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
From MaRDI portal
Publication:4210077
Recommendations
- scientific article; zbMATH DE number 1003266
- Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
- scientific article; zbMATH DE number 3876618
- Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs
- Improved algorithms for feedback vertex set problems
Cited in
(59)- Parameterised algorithms for deletion to classes of DAGs
- Constant ratio approximations of the weighted feedback vertex set problem for undirected graphs
- Packing cycles faster than Erdős-Pósa
- Towards a polynomial kernel for directed feedback vertex set
- Inapproximability of \(H\)-transversal/packing
- Towards a polynomial kernel for directed feedback vertex set
- An efficient algorithm for minimum feedback vertex sets in rotator graphs
- Minimum feedback vertex sets in shuffle-based interconnection networks
- An efficient local search for the feedback vertex set problem
- A linear time algorithm for the minimum-weight feedback vertex set problem in series-parallel graphs
- New formulae for the bipartite vertex frustration and decycling number of graphs
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- Combinatorial algorithms for feedback problems in directed graphs
- Fixed-parameter tractability for subset feedback set problems with parity constraints
- New upper bounds on feedback vertex numbers in butterflies
- A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
- Delaying decisions and reservation costs
- On the Complexity of Singly Connected Vertex Deletion
- Feedback vertex set in hypercubes
- 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.
- Feedback vertex sets on restricted bipartite graphs
- On the minimum feedback vertex set problem: Exact and enumeration algorithms
- Fixed-parameter tractability for the subset feedback set problem and the \(S\)-cycle packing problem
- Tracking paths
- Compact formulations and an iterated local search-based matheuristic for the minimum weighted feedback vertex set problem
- Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
- Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
- MIP formulations for induced graph optimization problems: a tutorial
- On the feedback number of 3-uniform linear extremal hypergraphs
- The power of linear-time data reduction for maximum matching
- Deterministic Algorithms for the Independent Feedback Vertex Set Problem
- Spin Glass approach to the feedback vertex set problem
- Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT
- Safe approximation and its relation to kernelization
- Maximum weighted induced forests and trees: new formulations and a computational comparative review
- The feedback arc set problem with triangle inequality is a vertex cover problem
- Feedback vertex sets in mesh-based networks
- The Power of Linear-Time Data Reduction for Maximum Matching
- On the decycling number of generalized Kautz digraphs
- New bounds on the decycling number of generalized de Bruijn digraphs
- Complexity of near-3-choosability problem
- Kernels for deletion to classes of acyclic digraphs
- Constant factor approximation for tracking paths and fault tolerant feedback vertex set
- The size of graphs with given feedback vertex number
- Fixed parameterized algorithms for generalized feedback vertex set problems
- Decycling bipartite graphs
- Feedback numbers of Kautz digraphs
- Erdős-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing
- On the complexity of singly connected vertex deletion
- Feedback numbers of de Bruijn digraphs
- Degreewidth: A New Parameter for Solving Problems on Tournaments
- Feedback arc number and feedback vertex number of Cartesian product of directed cycles
- Parameterized algorithms and data reduction for the short secluded s‐t‐path problem
- The decycling number of outerplanar graphs
- Two Hardness Results on Feedback Vertex Sets
- Hitting forbidden minors: approximation and kernelization
- scientific article; zbMATH DE number 7053376 (Why is no real title available?)
- On making a distinguished vertex of minimum degree by vertex deletion
This page was built for publication: Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4210077)
