Resumen

Desde la perspectiva de la teoría de grafos y la teoría combinatoria, obtenemos nuevos límites superiores para el número de nodos de codificación, que pueden caracterizar la complejidad de codificación de la red, tanto en redes de multidifusión acíclicas como cíclicas. A diferencia de trabajos anteriores, en nuestro análisis investigamos primero la red de multidifusión simple con tasa de fuente h=2, y después h≥2. Descubrimos que, para redes de multidifusión acíclicas factibles, nuestro límite superior es exactamente el límite inferior dado por M. Langberg et al. en 2006. Por lo tanto, la diferencia entre sus límites inferior y superior para redes multicast acíclicas factibles no existe. Basándonos en el nuevo límite superior, mejoramos la complejidad computacional dada por M. Langberg et al. en 2009. Además, estos resultados apoyan aún más la viabilidad de las firmas para la codificación de redes.

• Materias:Análisis Matemático Álgebra Ingeniería Matemática aplicada Lógica matemática
• Subjects:Mathematical Analysis Algebra Engineering Applied Mathematics Mathematical logic
• Palabras claves:redes multicast acíclicas factibles, m. langberg, codificación de redes, redes multicast cíclicas, nuevos límites superiores, red multicast simple, teoría combinatoria, complejidad computacional, codificación de nodos, acíclicas factibles
• Keywords:feasible acyclic multicast networks, m. langberg, network coding, cyclic multicast networks, new upper bounds, simple multicast network, combinatorics theory, computational complexity, encoding nodes, feasible acyclic