Том 5, серия 1, номер 3, 1998 г., Стр. 64-69

УДК 519.8
А. И. Сердюков
К задаче о максимальном остове ограниченного радиуса

Аннотация:
Рассматривается NP-трудная задача отыскания в полном реберно-взвешенном неориентированном графе максимального по весу остова радиуса не более $R>0$. Предлагается приближенный алгоритм с временной сложностью $O(n^2)$ и относительной погрешностью получаемого решения, не превосходящей $1/R$, где $n$ – число вершин в исходном графе.
Библиогр. 3.

Сердюков А. И. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

Статья поступила 13 апреля 1998 г.