Premium
An algorithm for finding a short closed spanning walk in a graph
Author(s) -
Takamizawa K.,
Nishizeki T.,
Saito N.
Publication year - 1980
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230100306
Subject(s) - mathematics , combinatorics , hamiltonian path , graph , hamiltonian (control theory) , strongly connected component , discrete mathematics , mathematical optimization
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 ( p 2 log p ) algorithm for finding such a closed spanning walk in a graph with p vertices satisfying our condition.