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

Standard

Алгоритм последовательного построения остовных минимальных ориентированных лесов. / Буслов, Василий Анатольевич.

In: Записки научных семинаров ПОМИ, Vol. 497, 2020, p. 5-25.

Research output: Contribution to journal › Article › peer-review

BibTeX

@article{3f0235d64f2d4b2ea945d9f192ed4eb6,

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

abstract = "Для взвешенного орграфа предложен эффективный алгоритм построения остовных лесов минимального веса для произвольного числа деревьев, вплоть до получения минимального остовного дерева, если оно существует. Алгоритм заключаются в последовательном увеличении числа дуг (уменьшении числа деревьев) с сохранением определённой степени родства между минимальными лесами при изменении числа деревьев. Доказана корректность алгоритма и определена его сложность. Результат работы алгоритма -- набор остовных минимальных лесов, состоящих из $k$ деревьев, для всех допустимых $k$. Его сложность не превышает $O(N^3)$. Библ. -- 15 назв.",

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

author = "Буслов, {Василий Анатольевич}",

year = "2020",

language = "русский",

volume = "497",

pages = "5--25",

journal = "ЗАПИСКИ НАУЧНЫХ СЕМИНАРОВ САНКТ-ПЕТЕРБУРГСКОГО ОТДЕЛЕНИЯ МАТЕМАТИЧЕСКОГО ИНСТИТУТА ИМ. В.А. СТЕКЛОВА РАН",

issn = "0373-2703",

publisher = "Санкт-Петербургское отделение Математического института им. В. А. Стеклова РАН",

}

RIS

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