Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem

DOI10.1016/0004-3702(95)00004-6zbMath1506.68118OpenAlexW2015905456MaRDI QIDQ2171258

Ann Becker, Dan Geiger

Publication date: 23 September 2022

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0004-3702(95)00004-6

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Related Items (32)

The size of graphs with given feedback vertex number ⋮ Hitting Weighted Even Cycles in Planar Graphs ⋮ Min (a)cyclic feedback vertex sets and MIN ones monotone 3-SAT ⋮ Using fractional primal-dual to schedule split intervals with demands ⋮ Towards a polynomial kernel for directed feedback vertex set ⋮ Parameterized complexity of secluded connectivity problems ⋮ Kernels for deletion to classes of acyclic digraphs ⋮ Meta-kernelization using well-structured modulators ⋮ Approximation and Kernelization for Chordal Vertex Deletion ⋮ Feedback vertex sets on restricted bipartite graphs ⋮ Inapproximability of $H$-Transversal/Packing ⋮ Tight Localizations of Feedback Sets ⋮ Approximating power node-deletion problems ⋮ A Linear Kernel for Planar Feedback Vertex Set ⋮ Minimum k‐cores and the k‐core polytope ⋮ A faster parameterized algorithm for pseudoforest deletion ⋮ Local search is a PTAS for feedback vertex set in minor-free graphs ⋮ Timeline cover in temporal graphs: exact and approximation algorithms ⋮ Circumventing connectivity for kernelization ⋮ Approximate Turing Kernelization for Problems Parameterized by Treewidth ⋮ On feedback vertex set: new measure and new structures ⋮ Polynomial kernels for deletion to classes of acyclic digraphs ⋮ An improved FPT algorithm for almost forest deletion problem ⋮ On making a distinguished vertex of minimum degree by vertex deletion ⋮ Approximability of the independent feedback vertex set problem for bipartite graphs ⋮ Polynomial-time algorithms for the subset feedback vertex set problem on interval graphs and permutation graphs ⋮ An approximation algorithm for the \(l\)-pseudoforest deletion problem ⋮ Combinatorial algorithms for feedback problems in directed graphs ⋮ Unnamed Item ⋮ A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs ⋮ Parameterised algorithms for deletion to classes of DAGs ⋮ A justification of local conditioning in Bayesian networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fusion, propagation, and structuring in belief networks
• Probabilistic inference in multiply connected belief networks using loop cutsets
• A Greedy Heuristic for the Set-Covering Problem
• Identifying independence in bayesian networks
• Fibonacci heaps and their uses in improved network optimization algorithms
• An algebra of bayesian belief universes for knowledge‐based systems

This page was built for publication: Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem