Improved approximation algorithms for hitting 3-vertex paths

DOI10.1007/s10107-019-01395-yzbMath1442.05222arXiv1808.10370OpenAlexW2941863476WikidataQ128007423 ScholiaQ128007423MaRDI QIDQ2191773

Oliver Schaudt, Samuel Fiorini, Gwenaël Joret

Publication date: 26 June 2020

Published in: Mathematical Programming. Series A. Series B, Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1808.10370

zbMATH Keywords

cluster vertex deletion

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (10)

The maximum independent union of cliques problem: complexity and exact approaches ⋮ \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs ⋮ Improved approximation algorithms for hitting 3-vertex paths ⋮ \(s\)-club cluster vertex deletion on interval and well-partitioned chordal graphs ⋮ Approximate association via dissociation ⋮ Polyhedral properties of the induced cluster subgraphs ⋮ On the \(d\)-claw vertex deletion problem ⋮ A tight approximation algorithm for the cluster vertex deletion problem ⋮ A tight approximation algorithm for the cluster vertex deletion problem ⋮ Approximation algorithms for hitting subgraphs

Cites Work

• Unnamed Item
• Approximate association via dissociation
• A primal-dual approximation algorithm for the vertex cover \(P^3\) problem
• Fixed-parameter algorithms for cluster vertex deletion
• Distance-hereditary graphs
• A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
• Improved approximation algorithms for hitting 3-vertex paths
• An Approximation Algorithm for Feedback Vertex Sets in Tournaments
• Fast Dynamic Graph Algorithms for Parameterized Problems
• A 7/3-Approximation for Feedback Vertex Sets in Tournaments
• A Fast Branching Algorithm for Cluster Vertex Deletion
• Inapproximability of $H$-Transversal/Packing

This page was built for publication: Improved approximation algorithms for hitting 3-vertex paths