6 papers
Faster Exponential-Time Approximate Counting via Bounded Self-Reductions
Katie Clinch, Serge Gaspers, Simon Mackenzie +1
We give faster exponential-time randomised approximation algorithms for counting problems where polynomial-time approximation is unavailable and exact exponential-time counting rem…
Stable cuts, NAC-colourings and flexible realisations of graphs
Katie Clinch, Dániel Garamvölgyi, John Haslegrave +3
A (2-dimensional) realisation of a graph is a pair , where maps the vertices of to . A realisation is flexible if it can be continuously deformed w…
Triangulated spheres with holes in triangulated surfaces
Katie Clinch, Sean Dewar, Niloufar Fuladi +6
Let denote a sphere with holes. Given a triangulation of a surface , we consider the question of when contains a spanning subgraph such t…
A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
Katie Clinch, Serge Gaspers, Tao Zixu He +2
This work introduces two techniques for the design and analysis of branching algorithms, illustrated through the case study of the Vertex Cover problem. First, we present a method…
Sharp thresholds for NAC-colourings and stable cuts in random graphs
Katie Clinch, John Haslegrave, Tony Huynh +1
NAC-colourings of graphs correspond to flexible quasi-injective realisations in . A special class of NAC-colourings are those that arise from stable cuts. We give s…
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…