42 citations · 132 across the 20 of their papers we have counts for
6 papers · 1 filter
A general lower bound for collaborative tree exploration
Yann Disser, Frank Mousset, Andreas Noever +2
We consider collaborative graph exploration with a set of agents. All agents start at a common vertex of an initially unknown graph and need to collectively visit all other ver…
Symmetric and asymmetric Ramsey properties in random hypergraphs
Luca Gugelmann, Rajko Nenadov, Yury Person +3
A celebrated result of Rödl and Ruciński states that for every graph , which is not a forest of stars and paths of length , and fixed number of colours there exist p…
Drift Analysis and Evolutionary Algorithms Revisited
Johannes Lengler, Angelika Steger
One of the easiest randomized greedy optimization algorithms is the following evolutionary algorithm which aims at maximizing a boolean function . The…
Polynomial Lower Bound for Distributed Graph Coloring in a Weak LOCAL Model
Dan Hefetz, Fabian Kuhn, Yannic Maus +1
We show an lower bound on the runtime of any deterministic distributed -graph coloring algorithm in a weak vari…
Local resilience for squares of almost spanning cycles in sparse random graphs
Andreas Noever, Angelika Steger
In 1962, Pósa conjectured that a graph contains a square of a Hamiltonian cycle if . Only more than thirty years later Komlós, Sárkőzy, and Szemerédi prove…
Unique reconstruction threshold for random jigsaw puzzles
Rajko Nenadov, Pascal Pfister, Angelika Steger
A random jigsaw puzzle is constructed by arranging square pieces into an grid and assigning to each edge of a piece one of available colours uniformly at ran…