Comunicación global en Grafos de Cayley.

He visto que se ha publicado hoy un paper (que aunque no tiene fecha, por un breve comentario y por las referencias parece del siglo pasado) que habla sobre este tema y que puede ser relevante para la patente y para la serie Sistemas RH (no lo se, dada su antigüedad).

TítuloGLOBAL COMMUNICATION ALGORITHMS FOR CAYLEY GRAPHS

Abstract.

We discuss several combinatorial problems that arise when one looks at computational algorithms for highly symmetric networks of processors. More specifically, we are interested in minimal times associated with four communication tasks (defined more precisely below):

–universal broadcast, every processor has a vector that it wishes to broadcast to all  the others;

–universal accumulation, every processor wishes to receive the
sum of all the vectors being sent to it by all the other processors;

–universal  exchange, every processor wishes to exchange a vector with each other processor; and global summation, every processor wants the sum of the
vectors in all the processors.

El comentario que me hace pensar que es antiguo es el siguiente:

This paper is adapted from and corrects errors in an unpublished internal report from Los Alamos National Laboratory [10].

La referencia [10] es de 1987. Y la referencia citada más reciente es de 1997. El autor, Vance Faber es conocido (al  menos tiene una página en wikipedia). Yo no lo conocía aunque tras leer el artículo de wikipedia ya me suena más (por la conjetura en la que aparece su nombre). Por lo visto es un experto sobre todo en procesamiento de imágenes, tema sobre el que mi conocimiento es de nulo a negativo. Trabajó unos 20 años en Los Alamos National Laboratory (hasta finales de los 90) y seguramente lo publicado en este paper lo hizo durante ese periodo.

Tras una primera lectura rápida, reconozco que a estas horas y al final del día, no lo entiendo todo. No habla, al menos explíticitamente, de recorridos hamiltonianos. Mañana más.

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: