36 citations · 61 across the 14 of their papers we have counts for
6 papers · 1 filter
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_…
Absorption Time of the Moran Process
Josep Diaz, Leslie Ann Goldberg, David Richerby +1
The Moran process models the spread of mutations in populations on graphs. We investigate the absorption time of the process, which is the time taken for a mutation introduced at a…
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…