9 citations · 42 across the 19 of their papers we have counts for
10 papers · 1 filter
Capturing an Invisible Robber using Separators
Igor Potapov, Tymofii Prokopenko, John Sylvester
We study the zero-visibility cops and robbers game, where the robber is invisible to the cops until they are caught. This differs from the classic game where full information about…
Rumors with Changing Credibility
Charlotte Out, Nicolás Rivera, Thomas Sauerwald +1
Randomized rumor spreading processes diffuse information on an undirected graph and have been widely studied. In this work, we present a generic framework for analyzing a broad cla…
Balanced Allocations with Heterogeneous Bins: The Power of Memory
Dimitrios Los, Thomas Sauerwald, John Sylvester
We consider the allocation of balls (jobs) into bins (servers). In the standard Two-Choice process, at each step we first sample two bins uniformly at rand…
The Power of Filling in Balanced Allocations
Dimitrios Los, Thomas Sauerwald, John Sylvester
We introduce a new class of balanced allocation processes which are primarily characterized by ``filling'' underloaded bins. A prototypical example is the Packing process: At each…
A New Temporal Interpretation of Cluster Editing
Cristiano Bocci, Chiara Capresi, Kitty Meeks +1
The NP-complete graph problem Cluster Editing seeks to transform a static graph into a disjoint union of cliques by making the fewest possible edits to the edges. We introduce a na…
Balanced Allocations: Caching and Packing, Twinning and Thinning
Dimitrios Los, Thomas Sauerwald, John Sylvester
We consider the sequential allocation of balls (jobs) into bins (servers) by allowing each ball to choose from some bins sampled uniformly at random. The goal is to maintai…
Multiple Random Walks on Graphs: Mixing Few to Cover Many
Nicolás Rivera, Thomas Sauerwald, John Sylvester
Random walks on graphs are an essential primitive for many randomised algorithms and stochastic processes. It is natural to ask how much can be gained by running multiple rando…
Time Dependent Biased Random Walks
John Haslegrave, Thomas Sauerwald, John Sylvester
We study the biased random walk where at each step of a random walk a "controller" can, with a certain small probability, move the walk to an arbitrary neighbour. This model was in…
The Power of Two Choices for Random Walks
Agelos Georgakopoulos, John Haslegrave, Thomas Sauerwald +1
We apply the power-of-two-choices paradigm to a random walk on a graph: rather than moving to a uniform random neighbour at each step, a controller is allowed to choose from two in…
The dispersion time of random walks on finite graphs
Nicolas Rivera, Alexandre Stauffer, Thomas Sauerwald +1
We study two random processes on an -vertex graph inspired by the internal diffusion limited aggregation (IDLA) model. In both processes particles start from an arbitrary bu…