"Записки научных семинаров ПОМИ"

Том 497, стр. 5-25

С.-Петербургский государственный университет, ул. Ульяновская, д.3, Старый Петергоф, 198504 Санкт-Петербург, Россия

abvabv@bk.ru, v.buslov@spbu.ru

Аннотация: Для взвешенного орграфа предложен эффективный алгоритм построения остовных лесов минимального веса для произвольного числа деревьев, вплоть до получения минимального остовного дерева, если оно существует. Алгоритм заключаются в последовательном увеличении числа дуг (уменьшении числа деревьев) с сохранением определённой степени родства между минимальными лесами при изменении числа деревьев. Доказана корректность алгоритма и определена его сложность. Результат работы алгоритма -- набор остовных минимальных лесов, состоящих из $k$ деревьев, для всех допустимых $k$. Его сложность не превышает $O(N^3)$. Библ. -- 15 назв.
Ключевые слова: взвешенный орграф, остовный подграф, минимальный лес [weighted digraph, spanning subgraph, minimal forest]