1 citations · 1 across the 6 of their papers we have counts for
6 papers
Constructions, bounds, and algorithms for peaceable queens
Katie Clinch, Matthew Drescher, Tony Huynh +1
The peaceable queens problem asks to determine the maximum number such that there is a placement of white queens and black queens on an chessboard…
BOBA: A Parallel Lightweight Graph Reordering Algorithm with Heavyweight Implications
Matthew Drescher, Muhammad A. Awad, Serban D. Porumbescu +1
We describe a simple parallel-friendly lightweight graph reordering algorithm for COO graphs (edge lists). Our ``Batched Order By Attachment'' (BOBA) algorithm is linear in the num…
A simple -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 and weight function , the Split Vert…
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…
A Tight Approximation Algorithm for the Cluster Vertex Deletion Problem
Manuel Aprile, Matthew Drescher, Samuel Fiorini +1
We give the first -approximation algorithm for the cluster vertex deletion problem. This is tight, since approximating the problem within any constant factor smaller than is…
Short rainbow cycles in graphs and matroids
Matt DeVos, Matthew Drescher, Daryl Funk +5
Let be a simple -vertex graph and be a colouring of with colours, where each colour class has size at least . We prove that contains a rainbow cycl…