Problemas de Programación Lineal en Redes de Información y Operadores de Clausura usando Particiones

Victor Peña-Macias, Humberto Sarria

Resumen


Una red de información es un grafo dirigido acíclico en el cual ciertos nodos llamados fuentes tienen mensajes que desean transmitir a otros nodos llamados receptores a través de la combinación de mensajes en nodos intermedios.

El problema de solubilidad consiste en encontrar una colección adecuada de funciones que permita combinar los mensajes en los nodos intermedios para que puedan ser decodificados donde son requeridos. En esta trabajo se estudia el problema de solubilidad fraccional de una red a través de una extensión del problema de solubilidad de un operador de clausura definido por Gadouleau en el 2013. Se definen problemas de programación lineal mediante dicha conexión con operadores de clausura para estudiar la capacidad de una red; usando algunas desigualdades de la información y desigualdades rango lineales dependientes de la característica se obtienen cotas superiores sobre la capacidad lineal de algunas redes y operadores de clausura sobre un cuerpo dado.

Palabras clave


Grafo dirigido; código de red; operador de clausura; matroide representable; desigualdad rango lineal

Texto completo:

PDF HTML

Referencias


Ahlswede R., Cai N., Li S.-Y. R. & Yeung R. W., Network information flow, IEEE Trans. Inform. Theory, 2000; 46:1204-1216 .

Blasiak A., Kleinberg R. & Lubetzky E., Lexicographic products and the power of non-Linear Network Coding, IEEE Symposium on Foundations of Computer Science, 2011; 609-618.

Brickell E. F. & Davenport D. M., On the classification of Ideal Secret Sharing, J. of Cryptology, 1991; 4:123-134.

Burris S. & Sankappanavar H. P., A course in Universal Algebra, Springer-Verlag 1981.

Dougherty R., Freiling C. & Zeger K., Insufficiency of linear coding in network information flow, IEEE Transactions on Information Theory, 2005; 51(8):2745-2759.

Dougherty R., Freiling C. & Zeger K., Networks, Matroids, and non-Shannon Information Inequalities, IEEE Trans. on Information Theory, 2007; 3(6):1949-1969.

Dougherty R., Freiling C. & Zeger K., Linear Rank Inequalities on five or more variables, arXiv:0910.0284 (2010).

Dougherty R., Freiling C. & Zeger K., Achievable Rate Regions for Network Coding, IEEE Transactions on Information Theory, 2015; 61(5):2488-2509.

Dougherty R. & Zeger K., Non-reversibility and equivalent constructions of Multiple-Unicast Networks, IEEE Transactions on Information Theory, 2006; 52(11):5067-5077

Gadouleau M., Closure solvability for Network Coding and Secret Sharing, IEEE Trans. Inform. Theory, UK , 2013; 59(12):7858-7869.

Matús, F., Matroid representations by partitions, Discrete Math., 1999; 203:169-194.

Mejía C., On the theory of linear rank inequalities, Tesis de Doctorado, Universidad Nacional de Colombia, Bogotá. Disponible en red, 2016.

Oxley J. G., Matroid Theory, Oxford Graduate Text in Mathematics, Department of Mathematics, Louisiana State University, 1992.

Peña V., Conexiones entre codificación en red, operadores de clausura y matroides de secreto compartido, Tesis de Maestría, Universidad Nacional de Colombia, Bogotá. Disponible en red, 2015.

Peña V. & Sarria H., How to find new Characteristic-Dependent Linear Rank Inequalities using binary matrices as a guide, 2019; ar-Xiv:1905.00003.

Riis S. & Gadouleau M., Graph-theoretical constructions for graph entropy and network coding based communications, IEEE Transactions on Information Theory, 2011; 57(10):6703-6717.

Seymour P. D., On secret-sharing matroids, Journal of Combinatorial Theory, 1992; B(56):69-73.

Shamir A., How to share a secret, Communications of the ACM, 1979; 22(11):612-613.

Shen A., Hammer D., Romashchenko A. E. & Vereshchagin N. K., Inequalities for Shannon entropy and Kolmogorov complexity, Journal of Computer and Systems Sciences, 2000; 60:442-464.

Simonis J. & Ashikhmin A., Almost affine codes, Des. Codes Cryptogr. 1998; 14:179-197.




DOI: http://dx.doi.org/10.17268/sel.mat.2019.02.12

Enlaces refback

  • No hay ningún enlace refback.


Short Title: Sel. mat.

---------------------------------------------------------------------------------------------------------

 ISSN:  2411-1783  Versión Electrónica.                      

---------------------------------------------------------------------------------------------------------------

Derechos reservados © 2014 Departamento de Matemáticas.

Para la distribución y cosecha de los Metadatos de nuestros artículos, usar el Protocolo de Interoperabilidad OAI-PMH:    http://revistas.unitru.edu.pe/index.php/SSMM/oai 

                 

                             E-mail: selecmat@unitru.edu.pe

Selecciones Matemáticas es una revista de la Universidad Nacional de Trujillo publica sus contenidos bajo licencia Creative Commons Attribution-NoComercial-ShareAlike 4.0.