10
$\begingroup$

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 ?

$\endgroup$

1 Answer 1

17
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Hey, that's a very cool paper! Thanks for the link. $\endgroup$
    – zotachidil
    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$
    – didest
    Jan 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.