Problemas de Programación Lineal en Redes de Información y Operadores de Clausura usando Particiones
DOI:
https://doi.org/10.17268/sel.mat.2019.02.12Palabras clave:
Grafo dirigido, código de red, operador de clausura, matroide representable, desigualdad rango linealResumen
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.Citas
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.
Publicado
Cómo citar
Número
Sección
Licencia
Los autores/as que publiquen en esta revista aceptan las siguientes condiciones:
- Los autores/as conservan los derechos de autor y ceden a la revista el derecho de la primera publicación, con el trabajo registrado con la licencia de atribución de Creative CommonsAtribución 4.0 Internacional (CC BY 4.0) , que permite a terceros utilizar lo publicado siempre que mencionen la autoría del trabajo y a la primera publicación en esta revista.
- Los autores/as pueden realizar otros acuerdos contractuales independientes y adicionales para la distribución no exclusiva de la versión del artículo publicado en esta revista (p. ej., incluirlo en un repositorio institucional o publicarlo en un libro) siempre que indiquen claramente que el trabajo se publicó por primera vez en esta revista.
- Se permite y recomienda a los autores/as a publicar su trabajo en Internet (por ejemplo en páginas institucionales o personales) antes y durante el proceso de revisión y publicación, ya que puede conducir a intercambios productivos y a una mayor y más rápida difusión del trabajo publicado(Consultar: efecto del acceso abierto).
