ГлавнаяАрхивПроверка соответствия ориентированного графа алгебраической решётке

Проверка соответствия ориентированного графа алгебраической решётке | Прикладная дискретная математика. 2018. № 41. DOI: 10.17223/20710410/41/6

Рассмотрена проблема проверки изоморфности ориентированного графа диаграмме некоторой решётки. Исследованы три типа конечных решёток, используемых в моделях разграничения доступа. Построен алгоритм проверки соответствия ориентированного графа прямому произведению решётки подмножеств и линейной решётки. Алгоритм основан на анализе структуры двух множеств: множества вершин, покрывающих ровно одну вершину, и множества атомарных вершин. Доказано, что вычислительная сложность алгоритма проверки не превосходит O(n3).
  • Title Проверка соответствия ориентированного графа алгебраической решётке
  • Headline Проверка соответствия ориентированного графа алгебраической решётке
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 41
  • Date:
  • DOI 10.17223/20710410/41/6
Ключевые слова
граф, теория 'решёток, мандатное разграничение доступа, graph, lattice theory, mandatory access control
Авторы
Ссылки
Belim S., Bogachenko N., and Ilushechkin E. An analysis of graphs that represent a role-based security policy hierarchy // J. Computer Security. 2015. V. 23. No. 5. P. 641-657.
Birkhoff G. Lattice Theory. N.Y.: Amer. Math. Soc. Colloquium Publ., 1967.
Jakubik J. On isomorphisms of graphs of lattices // Czechoslovak Math. J. 1985. V. 35. No. 2. P. 188-200.
Mainetti M. Arguesian identities in linear lattices // Adv. Math. 1999. No. 144. P. 50-93.
Mainetti M. and Yan C. H. Geometric identities in lattice theory // J. Combinatorial Theory. Ser.A. 2000. No. 91. P. 411-450.
Felsner S. and Knauer K. B. Distributive lattices from graphs // Proc. VI Jornadas de Matematica Discreta y Algoritmica. Lleida, 2008. P. 11-23.
Bertet K. The dependence graph of a lattice // Proc. CLA, Malaga, Spain, 2012. P. 223-231.
Belim S. V., Bogachenko N. F., Kabanov A. N., and Rakitskiy Yu. S. Using the Decision Support Algorithms Combining Different Security Policies // Dynamics of Systems, Mechanisms and Machines (Dynamics). 15-17 Nov. 2016. IEEE Xplore. http://ieeexplore.ieee.org/ document/7818976/.
Проверка соответствия ориентированного графа алгебраической решётке | Прикладная дискретная математика. 2018. № 41. DOI: 10.17223/20710410/41/6
Проверка соответствия ориентированного графа алгебраической решётке | Прикладная дискретная математика. 2018. № 41. DOI: 10.17223/20710410/41/6