Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications

DOI10.1137/S0895480195291874zbMath0941.68057OpenAlexW2072261513MaRDI QIDQ4490783

Baruch Schieber, Joseph (Seffi) Naor, Guy Even, 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

combinatorial optimizationapproximation algorithmsfeedback vertex setmulticutfeedback edge setsubset feedback set

Mathematics Subject Classification ID

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

Related Items (11)

Primal-dual approximation algorithms for feedback problems in planar graphs ⋮ Partitioning series-parallel multigraphs into \(v^*\)-excluding edge covers ⋮ Local search is a PTAS for feedback vertex set in minor-free graphs ⋮ A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem ⋮ A randomized polynomial kernel for subset feedback vertex set ⋮ Control of Boolean networks: hardness results and algorithms for tree structured networks ⋮ A primal-dual approximation algorithm for the vertex cover \(P^3\) problem ⋮ Subset Feedback Vertex Set Is Fixed-Parameter Tractable ⋮ On the minimum feedback vertex set problem: Exact and enumeration algorithms ⋮ A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs ⋮ Clustering with qualitative information

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