|
Интеллектуальные системы. Теория и приложения, 2022, том 26, выпуск 3, страницы 151–165
(Mi ista485)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Часть 3. Математические модели
Поиск семейства простых циклов в орграфе с полустепенями вершин, не превосходящими $ 2 $
А. А. Медведев Московский государственный технический университет имени Н. Э. Баумана
Аннотация:
Исследована алгоритмическая сложность задачи о поиске семейства простых циклов, обходящих каждую вершину орграфа с полустепенями вершин, не превосходящими $ 2$. Рассмотрены поисковый и оптимизационный ее варианты. Показана полиномиальная разрешимость задачи в обоих вариантах, предложен алгоритм со временем работы $ O(n^3) $, для частной постановки представлен алгоритм, требующий $ O(n^2) $ операций; $ n $ количество вершин орграфа.
Ключевые слова:
ориентированные графы, простые циклы, задачи поиска, оптимизация, класс $ P $, полиномиальная разрешимость.
Образец цитирования:
А. А. Медведев, “Поиск семейства простых циклов в орграфе с полустепенями вершин, не превосходящими $ 2 $”, Интеллектуальные системы. Теория и приложения, 26:3 (2022), 151–165
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ista485 https://www.mathnet.ru/rus/ista/v26/i3/p151
|
Статистика просмотров: |
Страница аннотации: | 24 | PDF полного текста: | 10 | Список литературы: | 5 |
|