TY  - SER
AU  - Медведев,Анатолий Александрович
TI  - Поиск семейства простых циклов в графах с полустепенями вершин, не превосходящими k
KW  - графы ориентированные
KW  - задачи поиска
KW  - простые циклы
KW  - полиномиальная разрешимость
KW  - статьи в журналах
N1  - Библиогр.: 19 назв
N2  - Исследована алгоритмическая сложность задачи о поиске семейства простых циклов, обходящих каждую вершину орграфа с полустепенями вершин, не превосходящими k, при наличии дополнительных ограничений на вид списка смежности. Рассмотрены поисковый и оптимизационный её варианты. Показана параметрически полиномиальная разрешимость задачи в обоих вариантах, предложены алгоритмы со временем работы O (nk 2 + n log2 n), O (n(k2 + k ) + n log2 n) и O(n) для различных типов ограничений; n — количество вершин орграфа
UR  - http://vital.lib.tsu.ru/vital/access/manager/Repository/koha:001003139
ER  -