Поиск семейства простых циклов в графах с полустепенями вершин, не превосходящими k

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

Add to "Quick Collection"

Description	Size	Format
Поиск семейства простых циклов в графах с полустепенями вершин, не превосходящими k	635 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/60/7

Title: Поиск семейства простых циклов в графах с полустепенями вершин, не превосходящими k
Title: Finding a family of simple circuits in graphs with vertex semidegrees bounded by k
Creator: Медведев, Анатолий Александрович
Date: 2023
DOI: 10.17223/20710410/60/7
Description: Исследована алгоритмическая сложность задачи о поиске семейства простых циклов, обходящих каждую вершину орграфа с полустепенями вершин, не превосходящими k, при наличии дополнительных ограничений на вид списка смежности. Рассмотрены поисковый и оптимизационный её варианты. Показана параметрически полиномиальная разрешимость задачи в обоих вариантах, предложены алгоритмы со временем работы O (nk 2 + n log2 n), O (n(k2 + k ) + n log2 n) и O(n) для различных типов ограничений; n — количество вершин орграфа.