39 citations · 89 across the 25 of their papers we have counts for
4 papers · 1 filter
On the approximability of the burning number
Anders Martinsson
The burning number of a graph is the smallest number such that the vertices of can be covered by balls of radii . As computing the burning number of a…
Synchronizing random automata through repeated 'a' inputs
Anders Martinsson
In a recent article by Chapuy and Perarnau, it was shown that a uniformly chosen automaton on states with a -letter alphabet has a synchronizing word of length $O(\sqrt{n}\l…
On Connectivity in Random Graph Models with Limited Dependencies
Johannes Lengler, Anders Martinsson, Kalina Petrova +4
For any positive edge density , a random graph in the Erdős-Renyi model is connected with non-zero probability, since all edges are mutually independent. We consider r…
Finding a good tree to burn
Anders Martinsson
The burning number of a graph is the smallest positive integer such that the vertex set of can be covered with balls of radii . A well-known conjectur…