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.12Palavras-chave:
Grafo dirigido, código de red, operador de clausura, matroide representable, desigualdad rango linealResumo
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.Referências
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
Como Citar
Edição
Seção
Licença
Os autores que publicam nesta revista aceitam as seguintes condições:
Os autores mantêm os direitos autorais e atribuem à revista o direito da primeira publicação, com o trabalho registrado com a licença de atribuição Creative Commons Atribución 4.0 Internacional (CC BY 4.0), que permite que terceiros usem o material publicado sempre que mencionarem a autoria do trabalho e os direitos autorais. Primeira publicação nesta revista.
Os autores podem fazer outros acordos contratuais independentes e adicionais para a distribuição não exclusiva da versão do artigo publicada nesta revista (por exemplo, incluí-la em um repositório institucional ou publicá-la em um livro), desde que afirme claramente que o trabalho Foi publicado nesta revista.
É permitido e recomendado aos autores que publiquem seus trabalhos na Internet (por exemplo, em páginas institucionais ou pessoais) antes e durante o processo de revisão e publicação, pois isso pode levar a trocas produtivas e a uma disseminação maior e mais rápida do trabalho. publicado (Consultar: efeito do acesso aberto).
