ID:14364
Type of Publication: Conference Proceedings
Authors: Zvi Lotker, Alfredo.Navarra
Title: Unbalanced points and vertices problem
ConferenceName: Proceedings - Fourth Annual IEEE International Conference on Pervasive Computing and Communications Workshops, PerCom Workshops 2006
Year: 2006
Volume: 2006
Pages: 96 - 100
Abstract: Starting from the Points and Vertices problem introduced in [9], given a graph G = (V, E] with |V|= n and a positive number ε, we consider the following problem. Place (1 - ε)n points on the vertices V of G independently and uniformly at random. Once the points are placed, relocate them by movements along the edges E of G using a function from the points to the vertices that minimizes the maximum distance between the random place of the points and their target vertices. The aim is to obtain in the final setting at most one point for each vertex. We look for an upper bound on this maximum relocation distance that holds with high probability over the initial placements of the points. We study several topologies for the graph G like paths, trees, d-dimensional grids, hypercubes and general graphs. © 2006 IEEE.
Keywords: Number theory;Graph theory;Probability;Topology;Trees (mathematics); ,
Last Updated: 9/4/2007 12:00:00 AM
Powered by Rami Palombo © 2005
Search in: Google Scholar  |  Scitation