Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
From MaRDI portal
Publication:4210077
DOI10.1137/S0097539796305109zbMATH Open0907.68110OpenAlexW2081880478MaRDI QIDQ4210077FDOQ4210077
Authors: Joseph (Seffi) Naor, Ron M. Roth, Reuven Bar-Yehuda, Dan Geiger 
Publication date: 20 September 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539796305109
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
Bayesian networkscombinatorial optimizationapproximation algorithmsconstraint satisfactionvertex feedback set
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) General topics in artificial intelligence (68T01)
Cited In (59)
- Delaying decisions and reservation costs
- MIP formulations for induced graph optimization problems: a tutorial
- Maximum weighted induced forests and trees: new formulations and a computational comparative review
- Complexity of near-3-choosability problem
- Constant factor approximation for tracking paths and fault tolerant feedback vertex set
- Degreewidth: A New Parameter for Solving Problems on Tournaments
- 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
- Inapproximability of \(H\)-transversal/packing
- Towards a polynomial kernel for directed feedback vertex set
- 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
- Fixed-parameter tractability for subset feedback set problems with parity constraints
- Combinatorial algorithms for feedback problems in directed graphs
- New upper bounds on feedback vertex numbers in butterflies
- On the Complexity of Singly Connected Vertex Deletion
- A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
- 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 set in hypercubes
- 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
- Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems
- 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
- On the feedback number of 3-uniform linear extremal hypergraphs
- Deterministic Algorithms for the Independent Feedback Vertex Set Problem
- The power of linear-time data reduction for maximum matching
- Spin Glass approach to the feedback vertex set problem
- Safe approximation and its relation to kernelization
- Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT
- The feedback arc set problem with triangle inequality is a vertex cover problem
- The Power of Linear-Time Data Reduction for Maximum Matching
- Feedback vertex sets in mesh-based networks
- New bounds on the decycling number of generalized de Bruijn digraphs
- On the decycling number of generalized Kautz digraphs
- Kernels for deletion to classes of acyclic digraphs
- Decycling bipartite graphs
- Fixed parameterized algorithms for generalized feedback vertex set problems
- The size of graphs with given feedback vertex number
- Erdős-Pósa property and its algorithmic applications: parity constraints, subset feedback set, and subset packing
- Feedback numbers of Kautz digraphs
- On the complexity of singly connected vertex deletion
- Feedback numbers of de Bruijn digraphs
- 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
- Title not available (Why is that?)
- The decycling number of outerplanar graphs
- Two Hardness Results on Feedback Vertex Sets
- Hitting forbidden minors: approximation and kernelization
- 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)
