Enumerando los k mejores caminos en orden de su longitud en DAGs
En este trabajo, consideramos el problema de los K mejores caminos conectando un par de nodos en un grafo sin ciclos dirigido (DAG) con longitudes arbitrarias. Demostramos que el árbol conteniendo el k-ésimo mejor camino difiere sólo en un arco con alguno de los (k-1) árboles conteniendo los (k-1) primeros mejores caminos. Esto nos permite diseñar un algoritmo de complejidad temporal O(m + K(n + logK)) y complejidad espacial O(K + m) para redes con longitudes reales. En el caso de DAGs con longitudes enteras la complejidad temporal se reduce a O(m + Kn). Un estudio computacional revela que el algoritmo propuesto supera en la práctica a los algoritmos existentes en la literatura.
Palabras clave: optimización combinatoria algoritmos de caminos mínimos k mejores soluciones
Otros trabajos en la misma sesión
Últimas noticias
-
22/04/12
Certificados -
11/03/12
Programa del congreso -
11/03/12
Cuota reducida -
15/01/12
Cuota superreducida
