An extension of the multi-path algorithm for finding Hamilton cycles (Q1197026)

Chistofides described the multi-path algorithm for finding Hamilton cycles in a graph \(G\). This algorithm is an intelligent exhaustive search for a Hamilton cycle. The author describes how this algorithm can be modified. He gives two ways for improving: (1) by detecting small separating sets \(M\) for which \(G-M\) has more than \(| M|\) components; and (2) by detecting bipartitions \((X,Y)\) with \(| X|<| Y|\). These conditions enable the algorithm to recognize, in certain cases, that \(G\) is non-Hamiltonian. The modifications are described in a pseudo-language.