Самый быстрый известный алгоритм для нахождения простых путей по заданному набору вершин

Для неориентированного графа и данного множество вершин, что является асимптотически быстрым известным алгоритма для нахождения простого пути , содержащий все элементы . Что, если мы требуем, чтобы путь был максимально коротким? $G$ $S$ $S$

ds.algorithms graph-algorithms time-complexity shuaoT
источник

Ответы:

См. Http://thorehusfeldt.files.wordpress.com/2010/08/soda2012_submission_247.pdf .

Андреас Бьёрклунд
источник

Эй, это очень классная статья! Спасибо за ссылку.

зотачидил

дополнительные очки за аккуратное украшение на первой странице. Как ты это сделал ?

Суреш Венкат

Очевидно ли, что алгоритм поиска цикла работает для пути?

didest

@Diego: Добавьте указанное ребро между двумя вершинами, которые вы хотите использовать в качестве конечных точек пути.

Андреас Бьёрклунд