For an undirected graph $G$ and a given set $S$ of vertices, what is the asymptotically fastest known algorithm for finding a simple path containing all elements of $S$. What if we require the path to be as short as possible ?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
answered Jan 10, 2012 at 14:11
-
$\begingroup$ Hey, that's a very cool paper! Thanks for the link. $\endgroup$ Jan 10, 2012 at 15:06
-
2$\begingroup$ extra points for the neat decoration on the front page. How did you do that ? $\endgroup$ Jan 10, 2012 at 16:59
-
$\begingroup$ is it obvious that an algorithm for finding a cycle works for a path? $\endgroup$– didestJan 10, 2012 at 17:40
-
3$\begingroup$ @Diego: Add a specified edge between the two vertices which you want to be endpoints of the path. $\endgroup$ Jan 10, 2012 at 17:54