"Записки научных семинаров ПОМИ"
Том 545, стр. 17-35
Алгоритм построения родственных остовных ориентированных лесов минимального веса
В. А. Буслов
Санкт-Петербургскй
государственный университет,
ул. Ульяновская, д.3, Старый Петергоф,
198504 Санкт-Петербург, Россия
abvabv@bk.ru, v.buslov@spbu.ru
- Аннотация:
Предложен алгоритм построения ориентированных остовных лесов минимального веса,
в котором сохраняется максимально возможная степень родства между
минимальными лесами при изменении числа деревьев. Проверена корректность
алгоритма и определена его сложность, которая не превышает $O(N^3)$
для плотных графов. Результатом работы алгоритма является набор
родственных остовных минимальных лесов, состоящих из $k$ деревьев,
для всех допустимых $k$.
Библ. -- 10 назв.
- Ключевые слова: взвешенный орграф, минимальный лес, цепь Маркова
[weighted digraph, minimum forest, Markov chain]
Полный текст(.pdf)