El problema del ancho de banda mínimo es encontrar un orden de los nodos del gráfico en la línea entera que minimiza la distancia más grande entre dos nodos adyacentes.
El problema de decisión es NP-completo incluso para árboles binarios. Resultados de complejidad para la minimización del ancho de banda. Garey, Graham, Johnson y Knuth, SIAM J. Appl. Math., Vol. 34, N ° 3, 1978 .
¿Cuál es el resultado de aproximación eficiente más conocido para calcular el ancho de banda mínimo en árboles binarios? ¿Cuál es la mejor dureza condicional conocida del resultado de aproximación?
fuente