New answers tagged hamiltonian-graphs
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.
...
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.&...
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....
Top 50 recent answers are included
Related Tags
hamiltonian-graphs × 106graph-theory × 96
co.combinatorics × 42
hamiltonian-paths × 18
reference-request × 8
computational-complexity × 6
random-graphs × 5
planar-graphs × 5
algorithms × 4
infinite-combinatorics × 4
recreational-mathematics × 4
bipartite-graphs × 4
nt.number-theory × 3
pr.probability × 3
discrete-geometry × 3
graph-colorings × 3
counterexamples × 3
extremal-graph-theory × 3
perfect-matchings × 3
triangulations × 3
directed-graphs × 3
cycles × 3
hypercube × 3
traveling-salesman-problem × 3
convex-polytopes × 2