Applied Graph Theory

The check of the correspondence of the directed graph to the algebraic lattice

S. V. Belim, N. F. Bogachenko

Dostoevsky Omsk State University, Omsk, Russia

Abstract: 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.

UDC: 004.056

DOI: 10.17223/20710410/41/6

Bibliographic databases:

• 
•