32 citations · 97 across the 48 of their papers we have counts for
9 papers · 1 filter
Optimal Grid Drawings of Complete Multipartite Graphs and an Integer Variant of the Algebraic Connectivity
Ruy Fabila-Monroy, Carlos Hidalgo-Toscano, Clemens Huemer +2
How to draw the vertices of a complete multipartite graph on different points of a bounded -dimensional integer grid, such that the sum of squared distances between vertices…
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_…
The Role of Visibility in Pursuit / Evasion Games
Athanasios Kehagias, Dieter Mitsche, Pawel Pralat
The cops-and-robber (CR) game has been used in mobile robotics as a discretized model (played on a graph G) of pursuit/evasion problems. The "classic" CR version is a perfect infor…
Cops and Invisible Robbers: the Cost of Drunkenness
Athanasios Kehagias, Dieter Mitsche, Pawel Pralat
We examine a version of the Cops and Robber (CR) game in which the robber is invisible, i.e., the cops do not know his location until they capture him. Apparently this game (CiR) h…
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…