Тип публикации: диссертация
Год издания: 2022
Ключевые слова: оптимизация, алгоритмы, гиперграф, граф, маршрутизация, максимальные индуцированные биклики
Аннотация: Целью диссертации является разработка алгоритмов комбинаторной оптимизации для решения задач маршрутизации и перечислительных задач, возникающих при анализе графовых и гиперграфовых сетей. В диссертации разработаны, реализованы в виде комплекса программ и протестированы на случайных и реальных данных новые алгоритмы для решения слеПоказать полностьюдующих задач: задачи о кратчайшем пути в нестационарной метрической сети с условием FIFO и ресурсоограниченной сети с одним ресурсом, задача поиска всех максимально полных подматриц матрицы инцидентности гиперграфа, задача перечислениях всех максимальных индуцированных биклик гиперграфа. Доказаны теоремы о временной сложности и корректности предложенных алгоритмов. Даны рекомендации по их практическому использованию для различных сетей. Разработанные алгоритмы могут применяться в геоинформационных, телекоммуникационных, навигационных системах. Представлен анализ модельной дорожной сети.