Starting from the points and vertices problem introduced in (R. Klasing and et al., 2005), given a graph G = (V, E) with |V| = n and a positive number isin, we consider the following problem. Place (1 - isin)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.

Unbalanced Points and Vertices Problem

NAVARRA, Alfredo
2006

Abstract

Starting from the points and vertices problem introduced in (R. Klasing and et al., 2005), given a graph G = (V, E) with |V| = n and a positive number isin, we consider the following problem. Place (1 - isin)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
9780769525204
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11391/159778
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
social impact