5 citations · 19 across the 20 of their papers we have counts for
6 papers · 1 filter
A probabilistic version of the game of Zombies and Survivors on graphs
Anthony Bonato, Dieter Mitsche, Xavier Pérez-Giménez +1
We consider a new probabilistic graph searching game played on graphs, inspired by the familiar game of Cops and Robbers. In Zombies and Survivors, a set of zombies attempts to eat…
On the relation between graph distance and Euclidean distance in random geometric graphs
Josep Díaz, Dieter Mitsche, Guillem Perarnau +1
Given any two vertices u, v of a random geometric graph, denote by d_E(u,v) their Euclidean distance and by d_G(u,v) their graph distance. The problem of finding upper bounds on d_…
A new upper bound for 3-SAT
J. Diaz, L. Kirousis, D. Mitsche +1
We show that a randomly chosen 3-CNF formula over n variables with clauses-to-variables ratio at least 4.4898 is, as n grows large, asymptotically almost surely unsatisfiable. The…
On the Probability of the Existence of Fixed-Size Components in Random Geometric Graphs
J. Diaz, D. Mitsche, X. Perez
In this work we give precise asymptotic expressions on the probability of the existence of fixed-size components at the threshold of connectivity for random geometric graphs.
Dynamic Random Geometric Graphs
Josep Diaz, Dieter Mitsche, Xavier Perez
In this work we introduce Dynamic Random Geometric Graphs as a basic rough model for mobile wireless sensor networks, where communication distances are set to the known threshold f…
Sharp threshold for hamiltonicity of random geometric graphs
J. Diaz, D. Mitsche, X. Perez
We show for an arbitrary norm that the property that a random geometric graph contains a Hamiltonian cycle exhibits a sharp threshold at $r=r(n)=\sqrt{\f…