El algoritmo más rápido conocido para encontrar rutas simples a través de un conjunto dado de vértices

Para un grafo no dirigido y un conjunto dado de vértices, lo que es el algoritmo asintóticamente más rápida conocida para encontrar un camino simple que contiene todos los elementos de . ¿Qué pasa si requerimos que el camino sea lo más corto posible? $G$ $S$ $S$

ds.algorithms graph-algorithms time-complexity shuaoT
fuente

Respuestas:

Ver http://thorehusfeldt.files.wordpress.com/2010/08/soda2012_submission_247.pdf .

Andreas Björklund
fuente

¡Hola, ese es un papel genial! Gracias por el enlace.

zotachidil

puntos extra por la cuidada decoración en la portada. Cómo hiciste eso ?

Suresh Venkat

¿Es obvio que un algoritmo para encontrar un ciclo funciona para una ruta?

Didest

@Diego: agregue un borde especificado entre los dos vértices que desea que sean puntos finales de la ruta.

Andreas Björklund