Approximation de la bande passante minimale sur les arbres binaires

Le problème de bande passante minimale consiste à trouver un ordre des nœuds de graphique sur une ligne entière qui minimise la plus grande distance entre deux nœuds adjacents.

Le problème de décision est NP-complet même pour les arbres binaires. Résultats de complexité pour la minimisation de la bande passante. Garey, Graham, Johnson et Knuth, SIAM J. Appl. Math., Vol. 34, n ° 3, 1978 .

Quel est le résultat d'approximation efficace le plus connu pour calculer la bande passante minimale sur les arbres binaires? Quelle est la dureté conditionnelle d'approximation la plus connue?

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

Cependant, pour certains types de graphiques, le problème peut être résolu ou approché en temps polynomial. Pour une enquête récente, voir Petit J., Addenda to the Survey of Layout Problems, 2011 . Dans l'enquête, voir les tableaux 3, 4 et 8. L'enquête donne également une belle liste de références si vous souhaitez approfondir une direction. Il s'agit d'une version plus mise à jour de l'ancienne enquête de Diaz et al., A survey of Graph Layout Problems, 2002 .

$O(4.83^n)$