Об одном обобщении задачи коммивояжера на максимум

Рассматривается задача поиска связного остовного подграфа с заданными степенями вершин максимального суммарного рёберного веса в полном взвешенном неориентированном графе. Для решения задачи представлен полиномиальный приближённый алгоритм. Проведён его анализ и обоснованы гарантированные оценки точности получаемых решений задачи в общем случае, а также в случаях метрической и евклидовой задач.
Библ. 9.