О некоторых полиномиально разрешимых случаях и приближённых алгоритмах для задачи построения оптимального коммуникационного дерева

В произвольном неориентированном $n$-вершинном графе с неотрицательными весами рёбер требуется построить остовное дерево, в котором сумма по всем вершинам максимальных весов инцидентных вершине рёбер минимальна. Найдены частные случаи полиномиальной разрешимости. Показано, что минимальный остов, веса рёбер которого принадлежат отрезку $[a,b]$, является $\bigl(2-\frac{2a}{a+b+2b/(n-2)}\bigr)$-приближённым решением и задача построения 1,00048-приближённого решения NP-трудна. Предложен эвристический полиномиальный алгоритм, и осуществлён его апостериорный анализ. Табл. 4, ил. 4, библиогр. 14.