Estoy buscando una implementación de un algoritmo para calcular el ancho de ruta de un gráfico. Es bien sabido que calcular el ancho de ruta es equivalente a calcular el número de búsqueda de nodos, el número de separación de vértices o el grosor de intervalo del gráfico. El algoritmo no tiene que ser muy rápido; Quiero ejecutarlo en gráficos de como máximo 20 vértices. Sí necesito el algoritmo para calcular el ancho de ruta exactamente, en lugar de dar una aproximación.
Soy consciente de que hay algunas implementaciones para calcular el ancho de árbol de un gráfico (un concepto relacionado), pero no he podido encontrar ninguna para calcular el ancho de ruta. Cualquier puntero es apreciado!
No sé sobre "una implementación" pero echa un vistazo
Ancho de ruta de cálculo más rápido que 2 ^ n Karol Suchan e Yngve Villanger Computación parametrizada y exacta, 4to Taller internacional, IWPEC 2009, Copenhague, Dinamarca, Springer Verlag, Lecture Notes in Computer Science 5917, páginas 324-335.
fuente
Hisao Tamaki ideó recientemente un algoritmo exacto para el ancho de ruta dirigido (WG 2011). Allí se refiere a una aplicación práctica exitosa de su enfoque (ISCIT 2010), por lo que supongo que también tiene una implementación del algoritmo.
Hisao Tamaki: Un enfoque de descomposición de ruta dirigida para identificar exactamente atractores de redes booleanas. Simposio internacional sobre comunicaciones y tecnologías de la información (ISCIT 2010), pp. 844-849
Hisao Tamaki: Algoritmo de tiempo polinómico para ancho de ruta dirigido delimitado. En: 37º Taller internacional sobre conceptos de teoría de grafos en informática (WG 2011), LNCS 6986, pp. 331-342.
fuente