Aproximación de ancho de banda mínimo en los árboles binarios

Question

problema mínimo ancho de banda es a un encontrar un ordenamiento de nodos de gráfico en la línea número entero que minimiza la distancia más grande entre dos nodos adyacentes.

El problema de decisión es NP-completo incluso para los árboles binarios. Complejidad Resultados para ancho de banda de minimización. Garey, Graham, Johnson y Knuth, SIAM J. Appl. Math., Vol. 34, Nº 3, 1978 .

¿Cuál es el resultado eficiente approximability más conocido para el cálculo de ancho de banda mínimo en los árboles binarios? Lo que es más conocido dureza condicional de aproximación resultado?

Answer 1

Blache et. otros, en la aproximación Intratabilidad del problema de ancho de banda de 1997 confirma que no hay PTAS para el problema a menos que $ \ text {P} = \ text {NP} $, incluso para (binario) árboles. Unger W, la complejidad de la aproximación del problema del ancho de banda, 1998 muestran que para cualquier constante k $ \ in \ mathbb {N} $ no hay ningún algoritmo de aproximación polinómica tiempo con un factor de aproximación de $ k $. Así que, por desgracia, no hay PTAS ni APX para el problema.

Sin embargo, para algunos tipos de gráficos, el problema puede ser resuelto o aproximar en tiempo polinómico. Para una encuesta reciente, véase Petit J., adiciones la Encuesta de diseño Problemas, 2011 . En la encuesta, véanse las Tablas 3, 4 y 8. La encuesta también da una buena lista de referencias si quieres cavar más profundo en cierta dirección. Se trata de una versión más actualizada de la encuesta por mayor Díaz et al. , Un estudio de diseño gráfico Problemas, 2002 .

En caso de estar interesado en el algoritmo exacto, así, creo que actualmente el más rápido está dada por Cygan M. y Pilipczuk M., aún más rápido Exact ancho de banda de 2012 . Las carreras de algoritmo en $ O (4.83 ^ n) $ tiempo.