Documents

  • p017.pdf

    532 KB, application/octet-stream

Предложен алгоритм построения ориентированных остовных лесов минимального веса, в котором сохраняется максимально возможная степень родства между минимальными лесами при изменении числа деревьев. Проверена корректность алгоритма и определена его сложность, которая не превышает $O(N^3)$ для плотных графов. Результатом работы алгоритма является набор родственных остовных минимальных лесов, состоящих из $k$ деревьев, для всех допустимых $k$.
Original languageRussian
Pages (from-to)17-35
Number of pages18
JournalЗАПИСКИ НАУЧНЫХ СЕМИНАРОВ САНКТ-ПЕТЕРБУРГСКОГО ОТДЕЛЕНИЯ МАТЕМАТИЧЕСКОГО ИНСТИТУТА ИМ. В.А. СТЕКЛОВА РАН
Volume545
StatePublished - Dec 2025

    Scopus subject areas

  • Mathematics(all)

ID: 145721835