List Price:
$15.00
Add to Cart
www.dharwadker.org

The Hamiltonian Circuit Algorithm
Authored by
Ashay Dharwadker
We present a new polynomialtime algorithm for finding Hamiltonian circuits in graphs. It is shown that the algorithm always finds a Hamiltonian circuit in graphs that have at least three vertices and minimum degree at least half the total number of vertices. In the process, we also obtain a constructive proof of Dirac's famous theorem of 1952, for the first time. The algorithm finds a Hamiltonian circuit (respectively, tour) in all known examples of graphs that have a Hamiltonian circuit (respectively, tour). In view of the importance of the P versus NP question, we ask: does there exist a graph that has a Hamiltonian circuit (respectively, tour) but for which this algorithm cannot find a Hamiltonian circuit (respectively, tour)? The algorithm is implemented in C++ and the program is demonstrated with several examples.
 Publication Date:
 20111002
 ISBN/EAN13:
 146638137X / 9781466381377
 Page Count:
 32
 Binding Type:
 US Trade Paper
 Trim Size:
 8.5" x 11"
 Language:
 English
 Color:
 Full Color
 Related Categories:
 Computers / Computer Science
