Проблема минимальной пропускной способности состоит в том, чтобы найти порядок узлов графа на целочисленной линии, который минимизирует наибольшее расстояние между любыми двумя соседними узлами.
Решение проблемы является NP-полным даже для бинарных деревьев. Результаты сложности для минимизации пропускной способности. Гэри, Грэм, Джонсон и Кнут, SIAM J. Appl. Math., Vol. 34, № 3, 1978 .
Каков наиболее известный результат эффективной аппроксимируемости для вычисления минимальной полосы пропускания на двоичных деревьях? Какова наиболее известная условная твердость результата аппроксимации?
источник