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

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
Проверка соответствия ориентированного графа алгебраической решетке	610 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/41/6

Title: Проверка соответствия ориентированного графа алгебраической решетке
Title: The check of the correspondence of the directed graph to the algebraic lattice
Creator: Белим, Сергей Викторович
|
Богаченко, Надежда Федоровна
Date: 2018
DOI: 10.17223/20710410/41/6
Description: Рассмотрена проблема проверки изоморфности ориентированного графа диаграмме некоторой решётки. Исследованы три типа конечных решёток, используемых в моделях разграничения доступа. Построен алгоритм проверки соответствия ориентированного графа прямому произведению решётки подмножеств и линейной решётки. Алгоритм основан на анализе структуры двух множеств: множества вершин, покрывающих ровно одну вершину, и множества атомарных вершин. Доказано, что вычислительная сложность алгоритма проверки не превосходит O(n3).