Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications
From MaRDI portal
Publication:4490783
DOI10.1137/S0895480195291874zbMath0941.68057MaRDI QIDQ4490783
Baruch Schieber, Guy Even, Joseph (Seffi) Naor, Leonid Zosin
Publication date: 20 July 2000
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
combinatorial optimization; approximation algorithms; feedback vertex set; multicut; feedback edge set; subset feedback set
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
A primal-dual approximation algorithm for the vertex cover \(P^3\) problem, Partitioning series-parallel multigraphs into \(v^*\)-excluding edge covers, 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, A factor \(2\) approximation algorithm for the vertex cover \(P_3\) problem, Clustering with qualitative information, Subset Feedback Vertex Set Is Fixed-Parameter Tractable