Документы

  • p017.pdf

    532 KB, application/octet-stream

Предложен алгоритм построения ориентированных остовных лесов минимального веса, в котором сохраняется максимально возможная степень родства между минимальными лесами при изменении числа деревьев. Проверена корректность алгоритма и определена его сложность, которая не превышает $O(N^3)$ для плотных графов. Результатом работы алгоритма является набор родственных остовных минимальных лесов, состоящих из $k$ деревьев, для всех допустимых $k$.
Язык оригиналарусский
Страницы (с-по)17-35
Число страниц18
ЖурналЗАПИСКИ НАУЧНЫХ СЕМИНАРОВ САНКТ-ПЕТЕРБУРГСКОГО ОТДЕЛЕНИЯ МАТЕМАТИЧЕСКОГО ИНСТИТУТА ИМ. В.А. СТЕКЛОВА РАН
Том545
СостояниеОпубликовано - дек 2025

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

  • Математика (все)

    Области исследований

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

ID: 145721835