New answers tagged

1 vote

Which are good algorithms for finding Hamiltonian path (not necessarily a circle) up to now?

For random graphs, there are algorithms that are efficient on average. See for example A fast algorithm on average for solving the Hamilton Cycle problem by Michael Anastos and the references therein. ...
Timothy Chow's user avatar
  • 78.1k
0 votes

Efficient Hamiltonian cycle algorithms for graph classes

Even though the Hamilton path problem is NP-hard, in practice it is usually easy. An efficient algorithm has been known for 50 years. It is "A Search Procedure for Hamilton Paths and Circuits.&...
Frank Rubin's user avatar
0 votes

Which are good algorithms for finding Hamiltonian path (not necessarily a circle) up to now?

The most efficient exact algorithm for finding Hamilton paths and circuits is "A Search Procedure for Hamilton Paths and Circuits." J. ACM 21 (Oct. 1974), pp 576-580; DOI: 10.1145/321850....
Frank Rubin's user avatar

Top 50 recent answers are included