Том 13, серия 2, номер 2, 2006 г., Стр. 3-20

УДК 519.8
А. Е. Бабурин, Э. Х. Гимади
Приближенный алгоритм поиска $d$-однородного связного остовного подграфа максимального веса в полном графе со случайными весами ребер

Аннотация:
Предложен приближeнный полиномиальный алгоритм для решения задачи поиска $d$-однородного связного остовного подграфа максимального веса в полном неориентированном взвешенном $n$-вершинном графе. Проведeн вероятностный анализ алгоритма для решения задачи со случайными входными данными (весами рeбер) в случае равномерного распределения весов рeбер и в случае распределений минорирующего типа. Показано, что предложенный алгоритм временно́й сложности $O(n^2+nd\ln n)$ находит асимптотически точное решение задачи при $d=o(n)$. В случае $d\leqslant n\ln n$ асимптотически точное решение может быть получено с временной сложностью $O(n^2)$. Для минимизационной версии задачи к условию асимптотической точности модифицированного алгоритма добавляется дополнительное ограничение на величину разброса значений весов рeбер графа.
Библ. 6.

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

Статья поступила 30 мая 2006 г.
Исправленный вариант — 2 ноября 2006 г.