The Hamiltonian Circuit Algorithm

Name: The Hamiltonian Circuit Algorithm
Rating: 5 (1 reviews)

Ashay Dharwadker

2004년 8월 · Institute of Mathematics

5.0

리뷰 1개

eBook

페이지

검증되지 않은 평점과 리뷰입니다. 자세히 알아보기

eBook 정보

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.

평점 및 리뷰

5.0

리뷰 1개

저자 정보

Ashay Dharwadker is the Distinguished Professor of Mathematics & Natural Sciences at the Institute of Mathematics, Gurgaon, India. He is the author of a dozen exquisitely illustrated books describing his fundamental contributions to combinatorics, graph theory, computer science and the foundations of physics.