Your Cart 
The Hamiltonian Circuit Algorithm

List Price: $15.00

Add to Cart

The Hamiltonian Circuit Algorithm

Authored by Ashay Dharwadker

We present a new polynomial-time 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:
146638137X / 9781466381377
Page Count:
Binding Type:
US Trade Paper
Trim Size:
8.5" x 11"
Full Color
Related Categories:
Computers / Computer Science

Site Help Order Help Policies Contact