logo móvil
Contáctanos

La difusión en estrellas de cliques y cliques conectados por caminos

Autores: Ambashankar, Akash; Harutyunyan, Hovhannes A.

Idioma: Inglés

Editor: MDPI

Año: 2025

Descargar PDF

Acceso abierto

Artículo científico
2025

La difusión en estrellas de cliques y cliques conectados por caminos


Categoría

Ingeniería y Tecnología

Subcategoría

Ingeniería de Software

Palabras clave

Transmisión
Red
Nodos
Algoritmo
Topología
Cliques

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 39

Citaciones: Sin citaciones


Descripción
La difusión es un problema fundamental de distribución de información en una red conectada donde un nodo, denominado originador, debe distribuir un mensaje a todos los demás nodos a través de una serie de llamadas a lo largo de los enlaces de la red. Una vez informados, los nodos ayudan al originador reenviando el mensaje a sus vecinos. Determinar el tiempo de difusión para un nodo en una red arbitraria es NP-completo. Si bien existen algoritmos de tiempo polinómico para topologías de red específicas, el problema sigue abierto para muchas otras. En este documento, nos enfocamos en abordar el problema de difusión en topologías de red representadas por estructuras especializadas basadas en cliques. Específicamente, investigamos el grafo de molino de viento, que consiste en cliques de tamaño conectadas a un nodo universal, y extendemos nuestro estudio a la estrella de cliques, una generalización del grafo de molino de viento con cliques de tamaños arbitrarios. Nuestro objetivo principal es proponer un algoritmo eficiente para determinar el tiempo de difusión de cualquier nodo en una estrella arbitraria de cliques y demostrar rigurosamente su optimalidad. Además, ampliamos el alcance examinando el problema de difusión en cliques conectadas por camino, una topología que presenta cliques de tamaños variables conectados secuencialmente a lo largo de un camino. Para esta estructura, desarrollamos un algoritmo computacionalmente eficiente que aprovecha los tamaños de los cliques y la adyacencia para optimizar las estrategias de difusión, con implicaciones más amplias para comprender la comunicación en grafos de bloques.

Otros recursos que podrían interesarte

Temas Virtualpro