Поиск семейства простых циклов в графах с полустепенями вершин, не превосходящими k А. А. Медведев
Material type:
ArticleContent type: Текст Media type: электронный Other title: Finding a family of simple circuits in graphs with vertex semidegrees bounded by k [Parallel title]Subject(s): графы ориентированные | задачи поиска | простые циклы | полиномиальная разрешимостьGenre/Form: статьи в журналах Online resources: Click here to access online
In:
Прикладная дискретная математика № 60. С. 85-94Abstract: Исследована алгоритмическая сложность задачи о поиске семейства простых циклов, обходящих каждую вершину орграфа с полустепенями вершин, не превосходящими k, при наличии дополнительных ограничений на вид списка смежности. Рассмотрены поисковый и оптимизационный её варианты. Показана параметрически полиномиальная разрешимость задачи в обоих вариантах, предложены алгоритмы со временем работы O (nk 2 + n log2 n), O (n(k2 + k ) + n log2 n) и O(n) для различных типов ограничений; n — количество вершин орграфа.
Библиогр.: 19 назв.
Исследована алгоритмическая сложность задачи о поиске семейства простых циклов, обходящих каждую вершину орграфа с полустепенями вершин, не превосходящими k, при наличии дополнительных ограничений на вид списка смежности. Рассмотрены поисковый и оптимизационный её варианты. Показана параметрически полиномиальная разрешимость задачи в обоих вариантах, предложены алгоритмы со временем работы O (nk 2 + n log2 n), O (n(k2 + k ) + n log2 n) и O(n) для различных типов ограничений; n — количество вершин орграфа.
There are no comments on this title.