Matthew Drescher

activity

20202024

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

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

collaborators

Showing math.COShow all

3 papers · 1 filter

math.CO2024

Constructions, bounds, and algorithms for peaceable queens

Katie Clinch, Matthew Drescher, Tony Huynh +1

The peaceable queens problem asks to determine the maximum number $a (n)$ such that there is a placement of $a (n)$ white queens and $a (n)$ black queens on an $n \times n$ chessboard…

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…

Constructions, bounds, and algorithms for peaceable queens

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

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

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