Сборники трудов ИСП РАН


Задача поиска путей в ациклических графах с ограничениями в терминах булевых грамматик

Шеметова Е.Н. (ИТМО, Санкт-Петербург, Россия)
Григорьев С.В. (СПбГУ, Санкт-Петербург, Россия)

Аннотация

Графовая модель данных активно используется в научных и прикладных областях, например, в графовых базах данных, биоинформатике, при анализе социальных сетей и в статическом анализе кода. Одной из основных задач, связанных с графовыми моделями, является поиск специфичных путей в графе. Естественным способом задать ограничения на пути являются формальные грамматики над метками рёбер графа, при этом запрос к графу может быть представлен в виде множества всех троек (A,v1,v2), для которых существует путь в графе от вершины v1 до вершины v2 такой, что метки на ребрах этого пути образуют строку, выводимую из нетерминала A в данной грамматике. Использование булевых грамматик позволяет формулировать более выразительные запросы по сравнению с традиционно используемыми регулярными и контекстно-свободными грамматиками. Известно, что задача выполнения запросов к графу с использованием булевых грамматик является неразрешимой. В данной работе предложен приближённый алгоритм поиска путей в ориентированных графах без циклов с ограничениями, заданными с помощью булевых грамматик. Благодаря ограничению на тип анализируемых графов, предложенный алгоритм является более асимптотически оптимальным, чем наивный итерационный алгоритм.

Ключевые слова

поиск путей с ограничениями; булевы грамматики; матричные операции; ациклический граф; булевы матрицы; произведение матриц

Издание

Труды Института системного программирования РАН, том 31, вып. 4, 2019, стр. 211-226.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2019-31(4)-14

Для цитирования

Шеметова Е.Н., Григорьев С.В. Задача поиска путей в ациклических графах с ограничениями в терминах булевых грамматик . Труды Института системного программирования РАН, том 31, вып. 4, 2019, стр. 211-226. DOI: 10.15514/ISPRAS-2019-31(4)-14.

Полный текст статьи в формате pdf Вернуться к содержанию тома