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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom