Алгоритм последовательного построения остовных минимальных ориентированных лесов

Результат исследований: Научные публикации в периодических изданияхстатьярецензирование

Аннотация

Для взвешенного орграфа предложен эффективный алгоритм построения остовных лесов минимального веса для произвольного числа деревьев, вплоть до получения минимального остовного дерева, если оно существует. Алгоритм заключаются в последовательном увеличении числа дуг (уменьшении числа деревьев) с сохранением определённой степени родства между минимальными лесами при изменении числа деревьев. Доказана корректность алгоритма и определена его сложность. Результат работы алгоритма -- набор остовных минимальных лесов, состоящих из $k$ деревьев, для всех допустимых $k$. Его сложность не превышает $O(N^3)$. Библ. -- 15 назв.
Язык оригиналарусский
Страницы (с-по)5-25
ЖурналЗаписки научных семинаров ПОМИ
Том497
СостояниеОпубликовано - 2020

Предметные области Scopus

  • Математика (все)
  • Компьютерные науки (все)

Ключевые слова

  • взвешенный орграф, остовный подграф, минимальный лес

Цитировать