Problem z minimalną przepustowością polega na znalezieniu kolejności węzłów wykresu na linii całkowitej, która minimalizuje największą odległość między dowolnymi dwoma sąsiadującymi węzłami.
Problem decyzyjny jest NP-zupełny nawet dla drzew binarnych. Wyniki złożoności dla minimalizacji przepustowości. Garey, Graham, Johnson and Knuth, SIAM J. Appl. Math., Vol. 34, nr 3, 1978 .
Jaki jest najbardziej znany efektywny wynik przybliżenia obliczania minimalnej przepustowości drzew binarnych? Jaka jest najbardziej znana twardość warunkowa wyniku aproksymacji?
źródło