On optimization problems for graphs and security of digital communications

V. A. Ustimenko<sup>ab

a</sup> University of Maria Curie-Sklodowska in Lublin (Poland)
^b Institute of telecommunications and global information space, Kiev, Natl. Acad. Sci. of Ukraine

Abstract: The most developed field of the classical Extremal Graph Theory studies the maximal size of simple graphs without certain cycles. We discuss resent results on the evaluation of the maximal size of digraphs without certain commutative diagrams that satisfy certain restrictions on the number of inputs and outputs (balanced digraphs or regular directed graphs). These studies are connected with problems of constructing LDPS Codes in Coding Theory and graph based stream ciphers and graph based public keys in Cryptography. Finally we show that the combinatorial optimization problems above can be formulated in the language of integer linear programming.

UDC: 519.1

Received: 31.03.2010

Language: English