4 papers
Balanced Facilities on Random Graphs
Roee David, Nimrod Talmon
Given a graph G with n vertices and k players, each of which is placing a facility on one of the vertices of G, we define the score of the i'th player to be the number of vertices…
On the Complexity of Closest Pair via Polar-Pair of Point-Sets
Roee David, Karthik C. S., Bundit Laekhanukit
Every graph can be represented by a collection of equi-radii spheres in a -dimensional metric such that there is an edge in if and only if the spheres correspon…
Random walks with the minimum degree local rule have cover time
Roee David, Uriel Feige
For a simple (unbiased) random walk on a connected graph with vertices, the cover time (the expected number of steps it takes to visit all vertices) is at most . We con…
On the effect of randomness on planted 3-coloring models
Roee David, Uriel Feige
We present the hosted coloring framework for studying algorithmic and hardness results for the -coloring problem. There is a class of host graphs. One selects a graph…