Neighbourhood of Constant Order in the Interval Graph of a Random Boolean Function

• Autorzy: Daubner J. , Toman E.
• Języki publikacji: EN

Abstrakty

EN

In the present paper we estimate the size of a neighbourhood of constant order in the interval graph of a random Boolean function. So far, no bound of this parameter has been known.

Słowa kluczowe

EN

random Boolean function; hypercube; interval graph; disjunctive normal form

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 122, nr 4
• Strony: 275--295
• Opis fizyczny: Bibliogr. 13 poz.

Twórcy

autor

Daubner J.

• University of Žilina, Faculty of Management Science and Informatics Department of Info Communication Networks Univerzitná 8215/1, 01026 Žilina, Slovakia

autor

Toman E.

• Comenius University, Faculty of Mathematics, Physics and Informatics Department of Computer Science Mlynská dolina, 842 48 Bratislava, Slovak Republic

Bibliografia

• [1] Daubner, J., Toman, E.: Vertex degree in the interval graph of a random Boolean function, Acta Mathematica Universitatis Comenianae, 79(2), 2010, 151–164.
• [2] Feller, W.: An Introduction to Probability Theory and its Application, 3rd Edition, J. Willey and Sons, New York, 1970.
• [3] Kostochka, A. V., Sapozhenko, A. A., Weber, K.: On random cubical graphs, In "Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity", J. Nešetˇril and M. Fiedler, Eds. Elsevier Science Publishers, 1992.
• [4] Škoviera, M.: On the minimization of random Boolean function I, Computers and Artificial Intelligence, 5(4), 1986, 321–334.
• [5] Škoviera, M.: On the minimization of random Boolean function II, Computers and Artificial Intelligence, 5(6), 1986, 493–509.
• [6] Palmer, E. M.: Graphical evolution, A Wiley-interscience publication, J. Willey and Sons, 1985.
• [7] Sapozhenko, A. A.: Disjunctive Normal Forms, Moscow University Press (in Russian), Moscow, 1975.
• [8] Sapozhenko, A. A.: Geometric structure of almost all Boolean functions, Problemy kibernetiki (in Russian), Moscow, 30, 1975, 227–261.
• [9] Toman, E.: On the size of a neighbourhood of the first rank, Computers and Artificial Intelligence, 12(2), 1993, 123–130.
• [10] Toman, E., Olejár, O., Stanek, M.: Average degree in the interval graph of a random Boolean function, Computing and Informatics, 27, 2008, 627–638.
• [11] Toman, E., Tomanová, J.: Some estimates of the complexity of disjunctive normal forms of a random Boolean function, Computers and Artificial Intelligence, 10(4), 1991, 327–340.
• [12] Yablonskij, S. V., Lupanov, O. B.: Discrete Mathematics and Mathematical Problems of Cybernetics, Nauka (in Russian), Moscow, 1974.
• [13] Zhuravlev, J. I.: Set theoretical methods in the algebra of logic, Problemy kibernetiki, Nauka, Moscow (in Russian), 8, 1962, 5–44.