Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications

DOI10.1137/S0895480195291874MaRDI QIDQ4490783zbMATH OpenOpenAlexFDO

Authors Guy Even, Joseph (Seffi) Naor, Baruch Schieber, Leonid Zosin

Publication date 20 July 2000

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0895480195291874

zbMATH Keywords

approximation algorithmscombinatorial optimizationfeedback edge setfeedback vertex setmulticutsubset feedback set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Approximating minimum feedback sets and multicuts in directed graphs
• Approximating minimum feedback sets and multi-cuts in directed graphs (extended summary)
• An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
• Constant factor approximation for subset feedback set problems via a new LP relaxation
• Primal-dual approximation algorithms for feedback problems in planar graphs

Cited in

(16)

• A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
• Approximating minimum feedback sets and multicuts in directed graphs
• Approximating minimum feedback vertex sets in hypergraphs
• A randomized polynomial kernel for subset feedback vertex set
• A factor 2 approximation algorithm for the vertex cover P₃ problem
• Local search is a PTAS for feedback vertex set in minor-free graphs
• Control of Boolean networks: hardness results and algorithms for tree structured networks
• Clustering with qualitative information
• An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
• Constant factor approximation for subset feedback set problems via a new LP relaxation
• Primal-dual approximation algorithms for feedback problems in planar graphs
• Approximating minimum feedback sets and multi-cuts in directed graphs (extended summary)
• A primal-dual approximation algorithm for the vertex cover P^3 problem
• Polyhedral aspects of feedback vertex set and pseudoforest deletion set
• Partitioning series-parallel multigraphs into v^*-excluding edge covers
• On the minimum feedback vertex set problem: Exact and enumeration algorithms

This page was built for publication: Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4490783)