Editing Hamiltonian path problem (section)

=== Partial paths ===
An early exact algorithm for finding a Hamiltonian cycle on a directed graph was the enumerative algorithm of Martello.<ref name="Held 1965 136–147"/> A search procedure by Frank Rubin<ref>{{citation |last=Rubin |first=Frank |title=A Search Procedure for Hamilton Paths and Circuits |journal=[[Journal of the ACM]] |volume=21 |issue=4 |pages=576–80 |year=1974 |doi=10.1145/321850.321854 |s2cid=7132716|doi-access=free }}</ref> divides the edges of the graph into three classes: those that must be in the path, those that cannot be in the path, and undecided. As the search proceeds, a set of decision rules classifies the undecided edges, and determines whether to halt or continue the search. Edges that cannot be in the path can be eliminated, so the search gets continually smaller. The algorithm also divides the graph into components that can be solved separately, greatly reducing the search size. In practice, this algorithm is still the fastest.