Geodesic
The check of the correspondence of the directed graph to the algebraic lattice
Prikladnaâ diskretnaâ matematika, no. 3 (2018), pp. 54-65.

Voir la notice de l'article provenant de la source Math-Net.Ru

The isomorphism check problem for a directed graph and a lattice diagram is considered in this paper. Three specific finite lattices used in the access control models are investigated. Special attention is paid to $MLS$-lattice which is the Cartesian product of the lattice of subsets and the linear lattice. Necessary and sufficient conditions for the isomorphism of a finite lattice $S$ to the $MLS$-lattice are found. For the lattice $S$, these conditions define some limitations to the number of all nodes, of atomic nodes, and of nodes covered by each element of the lattice $S$. An algorithm which checks the correspondence of the directed graph to the $MLS$-lattice is offered. This algorithm is based on the structure of two sets: the set of the nodes which cover exactly one node and the set of the atomic nodes. The following conditions are checked: the number of nodes of the directed graph $n=2^{n_1}n_2$; all nodes of the directed graph cover at least two others except the nodes $x_1,\dots,x_{n_1},t,t_1,\dots,t_{n_2-1}$, wherein $t$ is an outlet of the directed graph; the nodes $x_1,\dots,x_{n_1},t_1,\dots,t_{n_2-1}$ cover exactly one node; the nodes $x_1,\dots,x_{n_1},t_1$ are atomic nodes; the nodes $t_{n_2-1},\dots,t_1, t$ form a chain $t_{n_2-1}\succ\dots\succ t_1\succ t$ in which the nodes successively cover each other. We prove that the computing complexity of this algorithm does not exceed $\mathrm O(n^3)$.
Keywords: graph, lattice theory, mandatory access control. 
@article{PDM_2018_3_a5,
     author = {S. V. Belim and N. F. Bogachenko},
     title = {The check of the correspondence of the directed graph to the algebraic lattice},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {54--65},
     publisher = {mathdoc},
     number = {3},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2018_3_a5/}
}
TY  - JOUR
AU  - S. V. Belim
AU  - N. F. Bogachenko
TI  - The check of the correspondence of the directed graph to the algebraic lattice
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2018
SP  - 54
EP  - 65
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2018_3_a5/
LA  - ru
ID  - PDM_2018_3_a5
ER  - 
%0 Journal Article
%A S. V. Belim
%A N. F. Bogachenko
%T The check of the correspondence of the directed graph to the algebraic lattice
%J Prikladnaâ diskretnaâ matematika
%D 2018
%P 54-65
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2018_3_a5/
%G ru
%F PDM_2018_3_a5
S. V. Belim; N. F. Bogachenko. The check of the correspondence of the directed graph to the algebraic lattice. Prikladnaâ diskretnaâ matematika, no. 3 (2018), pp. 54-65. http://geodesic.mathdoc.fr/item/PDM_2018_3_a5/

[1] Belim S., Bogachenko N., Ilushechkin E., “An analysis of graphs that represent a role-based security policy hierarchy”, J. Computer Security, 23:5 (2015), 641–657 | DOI

[2] Birkhoff G., Lattice Theory, Amer. Math. Soc. Colloquium Publ., N.Y., 1967 | MR | Zbl

[3] Jakubik J., “On isomorphisms of graphs of lattices”, Czechoslovak Math. J., 35:2 (1985), 188–200 | MR | Zbl

[4] Mainetti M., “Arguesian identities in linear lattices”, Adv. Math., 144:1 (1999), 50–93 | DOI | MR | Zbl

[5] Mainetti M., Yan C. H., “Geometric identities in lattice theory”, J. Combinatorial Theory. Ser. A, 91:1–2 (2000), 411–450 | DOI | MR | Zbl

[6] Felsner S., Knauer K. B., “Distributive lattices from graphs”, Proc. VI Jornadas de Matematica Discreta y Algoritmica, Lleida, 2008, 11–23 | MR

[7] Bertet K., “The dependence graph of a lattice”, Proc. CLA, Malaga, Spain, 2012, 223–231

[8] Belim S. V., Bogachenko N. F., Kabanov A. N., Rakitskiy Yu. S., “Using the Decision Support Algorithms Combining Different Security Policies”, Dynamics of Systems, Mechanisms and Machines (Dynamics), IEEE Xplore, 15–17 Nov. 2016 http://ieeexplore.ieee.org/document/7818976/