Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
Алгоритм последовательного построения остовных минимальных ориентированных лесов. / Буслов, Василий Анатольевич.
в: Записки научных семинаров ПОМИ, Том 497, 2020, стр. 5-25.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - Алгоритм последовательного построения остовных минимальных ориентированных лесов
AU - Буслов, Василий Анатольевич
PY - 2020
Y1 - 2020
N2 - Для взвешенного орграфа предложен эффективный алгоритм построения остовных лесов минимального веса для произвольного числа деревьев, вплоть до получения минимального остовного дерева, если оно существует. Алгоритм заключаются в последовательном увеличении числа дуг (уменьшении числа деревьев) с сохранением определённой степени родства между минимальными лесами при изменении числа деревьев. Доказана корректность алгоритма и определена его сложность. Результат работы алгоритма -- набор остовных минимальных лесов, состоящих из $k$ деревьев, для всех допустимых $k$. Его сложность не превышает $O(N^3)$. Библ. -- 15 назв.
AB - Для взвешенного орграфа предложен эффективный алгоритм построения остовных лесов минимального веса для произвольного числа деревьев, вплоть до получения минимального остовного дерева, если оно существует. Алгоритм заключаются в последовательном увеличении числа дуг (уменьшении числа деревьев) с сохранением определённой степени родства между минимальными лесами при изменении числа деревьев. Доказана корректность алгоритма и определена его сложность. Результат работы алгоритма -- набор остовных минимальных лесов, состоящих из $k$ деревьев, для всех допустимых $k$. Его сложность не превышает $O(N^3)$. Библ. -- 15 назв.
KW - взвешенный орграф, остовный подграф, минимальный лес
UR - http://www.pdmi.ras.ru/znsl/2020/v497/abs005.html
M3 - статья
VL - 497
SP - 5
EP - 25
JO - ЗАПИСКИ НАУЧНЫХ СЕМИНАРОВ САНКТ-ПЕТЕРБУРГСКОГО ОТДЕЛЕНИЯ МАТЕМАТИЧЕСКОГО ИНСТИТУТА ИМ. В.А. СТЕКЛОВА РАН
JF - ЗАПИСКИ НАУЧНЫХ СЕМИНАРОВ САНКТ-ПЕТЕРБУРГСКОГО ОТДЕЛЕНИЯ МАТЕМАТИЧЕСКОГО ИНСТИТУТА ИМ. В.А. СТЕКЛОВА РАН
SN - 0373-2703
ER -
ID: 71718783