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

    Scopus subject areas

  • Mathematics(all)
  • Computer Science(all)

ID: 71718783