An algorithm for finding a short closed spanning walk in a graph
K. Takamizawa, T. Nishizeki, N. Saito · Networks · 1980
Abstract A Hamiltonian walk of a graph is a closed spanning walk of minimum length. In this paper we generalize a Dirac type sufficient condition ensuring the existence of a Hamiltonian cycle to one ensuring the existence of a closed spanning walk of length less than a specified value. Furthermore, we present an O (p2 log p) algorithm for finding such a closed spanning walk in a graph with p vertices satisfying our condition.