MaxDDBS

El problema del subgrafo con grado y diámetro máximos acotados (MaxDDBS) es un problema de la teoría de grafos .

Definición

Dado un grafo de hosts conectados $G$ , un límite superior para el grado $\Delta$ y un límite superior para el diámetro $D$ , buscamos el subgrafo más grande $S$ de $G$ con el grado máximo en la mayoría de los casos $\Delta$ y diámetro como máximo $D$ . ^{[ 1 ]}

Este problema también se conoce como el Problema del Subgrafo de Diámetro de Grado , ya que contiene el problema del diámetro de grado como un caso especial (es decir, al tomar un grafo completo suficientemente grande como grafo anfitrión). A pesar de ser una generalización natural del Problema del Diámetro de Grado , MaxDDBS solo comenzó a investigarse en 2011, mientras que la investigación en el Problema del Diámetro de Grado ha estado activa desde la década de 1960. ^{[ 1 ]}

También existe una versión ponderada del problema (MaxWDDBS) donde las aristas tienen pesos enteros positivos y el diámetro se mide como la suma de los pesos a lo largo del camino más corto. ^{[ 1 ]}

Complejidad computacional

En cuanto a su complejidad computacional, el problema es NP-difícil y no pertenece a APX (es decir, no se puede aproximar con un factor constante en tiempo polinomial ). ^{[ 2 ]} El problema sigue siendo NP-difícil incluso cuando se restringe a una sola restricción (ya sea grado o diámetro). ^{[ 1 ]}

El problema del subgrafo con el grado más grande acotado es NP-difícil cuando el subgrafo debe estar conectado, mientras que el problema del subgrafo con el diámetro máximo acotado se convierte en el problema de la camarilla máxima para $D=1$ , que fue uno de los 21 problemas NP-completos de Karp . ^{[ 1 ]}

Límites y relaciones

El orden de cualquier grafo con grado máximo $\Delta$ y diámetro $D$ no puede exceder el límite de Moore : ^{[ 1 ]}

M_{\Delta,D}=1+\Delta +\Delta (\Delta -1)+\cdots +\Delta (\Delta -1)^{D-1}

Este límite también sirve como límite superior teórico para MaxDDBS. Si denotamos por $N_{\Delta ,D}$ el orden del grafo más grande con grado máximo $\Delta$ y diámetro $D$ , entonces para cualquier solución $S$ de MaxDDBS con $n$ vértices:

n\leq N_{\Delta ,D}\leq M_{\Delta ,D}

Aplicaciones

MaxDDBS tiene diversas aplicaciones prácticas: ^{[ 1 ]}

Computación paralela y distribuida : El tiempo de comunicación es crucial en el procesamiento paralelo . Identificar una subred de grado y diámetro limitados dentro de una arquitectura paralela permite una computación eficiente.
Seguridad de redes y botnets : En el análisis de botnets , los atacantes pueden seleccionar subredes con restricciones específicas de grado y diámetro para maximizar el daño y evitar ser detectados. Comprender MaxDDBS ayuda a predecir los parámetros de la red de ataque y a desarrollar medidas defensivas.
Redes biológicas : Este problema se ha aplicado a redes de interacción de proteínas para identificar los núcleos de la red. Delimitar tanto el grado como el diámetro (en lugar de solo el diámetro) puede revelar patrones de interacción más complejos.

Algoritmos

Se ha propuesto un algoritmo heurístico voraz para MaxWDDBS con una relación de aproximación en el peor de los casos de ${\frac {\min(n,N_{\Delta ,D})}{\Delta +1}}$ , dónde $n$ es el número de vértices en el grafo anfitrión. ^{[ 1 ]} El algoritmo comienza con un $\Delta$ -estrella y hace crecer el subgrafo agregando aristas incidentes a vértices vivos hasta que no se puedan agregar más aristas manteniendo la restricción de grado.

Para la variante limitada por diámetro, existe un algoritmo con una razón de aproximación $O(n^{1/2})$ . ^{[ 1 ]}

Estudios experimentales en diversos grafos anfitriones muestran que el algoritmo voraz a menudo funciona significativamente mejor de lo que sugiere su límite teórico en el peor de los casos, como en grafos antiprisma o grafos aleatorios (modelos de Watts-Strogatz y Barabási-Albert). ^{[ 1 ]}

Casos especiales en gráficos de host específicos

El problema se ha estudiado para varias familias de grafos anfitriones, estableciéndose límites para redes de malla, hipercubos, redes de panal, redes triangulares, redes de mariposa, redes de Beneš y redes de óxido. ^{[ 3 ]}

redes malladas

Cuando el gráfico del host es un $k$ malla -dimensional , el problema se relaciona con el conteo de puntos de la red en bolas bajo la métrica $L$ $1$ . ^[²^]

Para una malla con $\Delta =2k$ , el subgrafo más grande contiene tantos vértices como puntos de la red en una bola cerrada de radio $D/2$ . ^{[ 2 ]}

El número de puntos de la red $|B_{k}(p)|$ en una bola máxima de radio $p$ en $k$ Las dimensiones vienen dadas por: ^{[ 2 ]}

Para un diámetro uniforme $D=2p$ Estos son los números de Delannoy.

Para diámetro impar $D=2p+1$ : Estas forman una matriz de Riordan de secuencias de coordinación

Se han desarrollado construcciones específicas para: ^{[ 2 ]}

Malla 3D con $\Delta =4$ $\Delta =4$ :
- Logros ${\frac {4p^{3}}{3}}+2p^{2}-{\frac {4p}{3}}+3$ vértices para $D=2p$
Malla 2D con $\Delta =3$ $\Delta =3$ :
- Logros $2p^{2}-2p+1$ vértices para $D=2p$

Estas construcciones son asintóticamente óptimas, con un grado promedio que se aproxima a $\Delta$ como $p\to \infty$ .

Hipercubo

Para el $k$ hipercubo dimensional $Q_{k}$ , cuando $D\leq \Delta$ , existe un subcubo $Q_{\Delta }$ que contiene un subgrafo de orden:

\Phi _{\Delta }(D)=\sum _{i=0}^{D}{\binom {\Delta }{i}}

Esto representa el volumen de una bola de Hamming de radio $D$ . ^{[ 1 ]}

Enlaces externos

La página de MaxDDBS en la Wiki de Combinatoria

Referencias

1 2 3 4 5 6 7 8 9 10 11 Dekker, A.; Pérez-Rosés, H.; Pineda-Villavicencio, G.; Watters, P. (2012). "El subgrafo de grado máximo y diámetro limitado y sus aplicaciones" . Journal of Mathematical Modelling and Algorithms . doi : 10.1007/s10852-012-9182-8 .
1 2 3 4 5 Miller, Mirka; Pérez-Rosés, Hebert; Ryan, Joe (2012). "El subgrafo de grado máximo y diámetro limitado en la malla". Matemáticas Aplicadas Discretas . 160 (12): 1782– 1790. doi : 10.1016/j.dam.2012.03.035 .
↑ Wijerathne, HMC; Lanel, GHJ; Perera, KKKR (2021). Revisión del problema del subgrafo acotado de diámetro de grado máximo (PDF) . Actas de la Conferencia Internacional SLIIT sobre Avances en Ciencias y Humanidades. págs. 12–24 .

[dpr12-1] 1 2 3 4 5 6 7 8 9 10 11 Dekker, A.; Pérez-Rosés, H.; Pineda-Villavicencio, G.; Watters, P. (2012). "El subgrafo de grado máximo y diámetro limitado y sus aplicaciones" . Journal of Mathematical Modelling and Algorithms . doi : 10.1007/s10852-012-9182-8 .

[mprr12-2] 1 2 3 4 5 Miller, Mirka; Pérez-Rosés, Hebert; Ryan, Joe (2012). "El subgrafo de grado máximo y diámetro limitado en la malla". Matemáticas Aplicadas Discretas . 160 (12): 1782– 1790. doi : 10.1016/j.dam.2012.03.035 .

[wlp21-3] Wijerathne, HMC; Lanel, GHJ; Perera, KKKR (2021). Revisión del problema del subgrafo acotado de diámetro de grado máximo (PDF) . Actas de la Conferencia Internacional SLIIT sobre Avances en Ciencias y Humanidades. págs. 12–24 .

[ 1 ]

[ 2 ]

[ 3 ]