Matthew Drescher

activity

20182024

most citedBOBA: A Parallel Lightweight Graph Reordering Algorithm with Heavyweight Implications

1 citations · 1 across the 6 of their papers we have counts for

collaborators

Showing 2020Show all

3 papers · 1 filter

math.CO2020

A simple $(2 + ε)$ -approximation algorithm for Split Vertex Deletion

Matthew Drescher, Samuel Fiorini, Tony Huynh

A split graph is a graph whose vertex set can be partitioned into a clique and a stable set. Given a graph $G$ and weight function $w : V (G) \to Q_{\geq 0}$ , the Split Vert…

math.CO2020

A simple 7/3-approximation algorithm for feedback vertex set in tournaments

Manuel Aprile, Matthew Drescher, Samuel Fiorini +1

We show that performing just one round of the Sherali-Adams hierarchy gives an easy 7/3-approximation algorithm for the Feedback Vertex Set (FVST) problem in tournaments. This matc…

math.CO2020

A Tight Approximation Algorithm for the Cluster Vertex Deletion Problem

Manuel Aprile, Matthew Drescher, Samuel Fiorini +1

We give the first $2$ -approximation algorithm for the cluster vertex deletion problem. This is tight, since approximating the problem within any constant factor smaller than $2$ is…

A simple (2+ε)-approximation algorithm for Split Vertex Deletion

A simple 7/3-approximation algorithm for feedback vertex set in tournaments

A Tight Approximation Algorithm for the Cluster Vertex Deletion Problem

A simple $(2 + ε)$ -approximation algorithm for Split Vertex Deletion