Algoritmo mais rápido conhecido para encontrar caminhos simples através de um determinado conjunto de vértices

10

Para um grafo não direcionado e um determinado conjunto de vértices, o que é o algoritmo assintoticamente mais rápido conhecido por encontrar um caminho simples contendo todos os elementos de . E se exigirmos que o caminho seja o mais curto possível?GSS

shuaoT
fonte

Respostas:

17

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

Andreas Björklund
fonte
Ei, esse é um papel muito legal! Obrigado pelo link.
Zotachidil
2
pontos extras pela decoração elegante na primeira página. Como você fez isso ?
Suresh Venkat
é óbvio que um algoritmo para encontrar um ciclo funciona para um caminho?
didest
3
@ Diego: Adicione uma aresta especificada entre os dois vértices que você deseja que sejam pontos finais do caminho.
Andreas Björklund