Constant Factor Approximation for Subset Feedback Set Problems via a new LP relaxation
From MaRDI portal
Publication:4575637
DOI10.1137/1.9781611974331.ch58zbMath1410.68288OpenAlexW4240459070MaRDI QIDQ4575637
Publication date: 16 July 2018
Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/1.9781611974331.ch58
Programming involving graphs or networks (90C35) Linear programming (90C05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items
Towards constant-factor approximation for chordal/distance-hereditary vertex deletion ⋮ Towards a polynomial kernel for directed feedback vertex set ⋮ Kernels for deletion to classes of acyclic digraphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterised algorithms for deletion to classes of DAGs