|
Дискретный анализ и исследование операций, сер. 1, 1998, том 5, выпуск 3, страницы 64–69
(Mi da362)
|
|
|
|
К задаче о максимальном остове ограниченного радиуса
А. И. Сердюков Институт математики им. С. Л. Соболева СО РАН
Аннотация:
Рассматривается NP-трудная задача отыскания в полном реберно-взвешенном неориентированном графе максимального по весу остова радиуса не более $R>0$. Предлагается приближенный алгоритм с временной сложностью $O(n^2)$ и относительной погрешностью получаемого решения, не превосходящей $1/R$, где $n$ – число вершин в исходном графе. Библиогр. 3.
Статья поступила: 13.04.1998
Образец цитирования:
А. И. Сердюков, “К задаче о максимальном остове ограниченного радиуса”, Дискретн. анализ и исслед. опер., сер. 1, 5:3 (1998), 64–69
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da362 https://www.mathnet.ru/rus/da/v5/s1/i3/p64
|
Статистика просмотров: |
Страница аннотации: | 182 | PDF полного текста: | 78 |
|