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
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
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.
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.