Том 13, серия 1, номер 3, 2006 г., Стр. 3-12
УДК 519.8
А. Е. Бабурин, Э. Х. Гимади
Об одном обобщении задачи коммивояжера на максимум
Аннотация:
Рассматривается задача поиска связного остовного подграфа с заданными степенями вершин максимального суммарного рёберного веса в полном взвешенном неориентированном графе. Для решения задачи представлен полиномиальный приближённый алгоритм. Проведён его анализ и обоснованы гарантированные оценки точности получаемых решений задачи в общем случае, а также в случаях метрической и евклидовой задач.
Библ. 9.
Бабурин А. Е. 1
Гимади Э. Х. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Статья поступила 9 марта 2006 г.
