Constant factor approximation for subset feedback set problems via a new LP relaxation

DOI10.1137/1.9781611974331.CH58MaRDI QIDQ4575637zbMATH OpenOpenAlexFDO

Authors Chandra Chekuri, Vivek Madan

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Linear programming (90C05) Programming involving graphs or networks (90C35)

Recommendations

• An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
• Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications
• Approximating minimum feedback sets and multi-cuts in directed graphs (extended summary)
• Approximating minimum feedback sets and multicuts in directed graphs
• A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs

Cited in

(11)

• Kernels for deletion to classes of acyclic digraphs
• Towards constant-factor approximation for chordal/distance-hereditary vertex deletion
• Parameterised algorithms for deletion to classes of DAGs
• Towards a polynomial kernel for directed feedback vertex set
• Approximating Minimum Subset Feedback Sets in Undirected Graphs with Applications
• An 8-Approximation Algorithm for the Subset Feedback Vertex Set Problem
• Towards a polynomial kernel for directed feedback vertex set
• scientific article; zbMATH DE number 7765420 (Why is no real title available?)
• Polyhedral aspects of feedback vertex set and pseudoforest deletion set
• Combinatorial optimization. Abstracts from the workshop held November 10--15, 2024
• Wannabe bounded treewidth graphs admit a polynomial kernel for directed feedback vertex set

This page was built for publication: Constant factor approximation for subset feedback set problems via a new LP relaxation

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