4 citations · 28 across the 18 of their papers we have counts for
4 papers · 1 filter
Building Hamiltonian Cycles in the Semi-Random Graph Process in Less Than Rounds
Alan Frieze, Pu Gao, Calum MacRury +2
The semi-random graph process is an adaptive random graph process in which an online algorithm is initially presented an empty graph on vertices. In each round, a vertex is…
Random-order Contention Resolution via Continuous Induction: Tightness for Bipartite Matching under Vertex Arrivals
Calum MacRury, Will Ma
We introduce a new approach for designing Random-order Contention Resolution Schemes (RCRS) via exact solution in continuous time. Given a function ,…
Online Bipartite Matching in the Probe-Commit Model
Allan Borodin, Calum MacRury
We consider the classical online bipartite matching problem in the probe-commit model. In this problem, when an online vertex arrives, its edges must be probed to determine if they…
Extending Wormald's Differential Equation Method to One-sided Bounds
Patrick Bennett, Calum MacRury
In this note, we formulate a "one-sided" version of Wormald's differential equation method. In the standard "two-sided" method, one is given a family of random variables which evol…