A simple linear expected time algorithm for finding a Hamiltonian path

A simple linear expected time algorithm for finding a Hamiltonian path

0.00 Avg rating—0 Votes
Article ID: iaor19881191
Country: Netherlands
Volume: 43
Start Page Number: 373
End Page Number: 379
Publication Date: Jun 1989
Journal: Annals of Discrete Mathematics
Authors:
Keywords: combinatorial analysis, programming: travelling salesman
Abstract:

The paper gives a simple algorithm which either finds a hamilton path between two specified vertices of a graph G of order n, or shows that no such path exists. If the probability of an edge in G is p≥12n’¸-1’/3 the algorithm runs in expected time cnp’¸-1 and uses storage cn, where c is an absolute constant.

Reviews

Required fields are marked *. Your email address will not be published.