Przybliżenie minimalnej przepustowości drzew binarnych

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?

$\text{P} = \text{NP}$$k \in \mathbb{N}$$k$

Jednak w przypadku niektórych typów wykresów problem można rozwiązać lub aproksymować w czasie wielomianowym. Najnowsze ankiety znajdują się w Petit J., Addenda to the Survey of Layout Problems, 2011 . W ankiecie zobacz Tabele 3, 4 i 8. Ankieta zawiera również ładną listę referencji, jeśli chcesz sięgnąć głębiej w jakimś kierunku. Jest to bardziej zaktualizowana wersja starszej ankiety przeprowadzonej przez Diaz i wsp., A ankieta of Graph Layout Problems, 2002 .

$O(4.83^n)$