Site Map Guestbook News Support Download / Purchase Efficiency Testlab About

Hamiltonian Cycle Problem
Company
Feedback
PCGrates
PCGrate-S(X) Series
PCGrates Screenshots
PCGrates Examples
Our Customers
NP-Complete Problems
Traveling Salesman Problem
Hamiltonian Cycle Problem
NP-Complete Problems Screenshots
NP-Complete Problems Examples
References
Currently available computer systems which claim to provide solutions to Hamiltonian Cycle problems within a reasonable time employ methods having method steps based on approximation of exact solutions. Accordingly, these systems cannot be relied upon where an exact solution to an NP-complete type problem is required.  
 
Other attempts have been made to model Hamiltonian networks using resistive circuits. Studies have shown that a minimum Hamiltonian cycle can be defined by Kirchhoff's equations. Nevetherless, as is the case with existing computer-implemented methods, problems have been noted in the accuracy attainable with methods on physical modeling1.  
Over the last decads I.I.G., Inc. specialists have been actively pursuing investigations of NP-completeness in different areas of discrete mathematics (Appl. No. 09/006,367, US Patent No. 6,636,840 B11, Appl. No. 10/438,305).  
 
We make it possible for all who wish to become acquainted with the code "HCP Solver", which was developed for finding a cycle in special graphs generated with the use of generator "Leaper" (TSPLIB/HCP). The optimization algorithm "HCP Solver" is an approximate polynomial algorithm with O(N3). It is based on the concept of successive iterative decreases in cycle length, in which the iterative procedure begins with a randomly chosen cycle. As different edges of the graph are assigned the weights 0 and 1, the cycle length is determined in view of the edges with the unit weight. Each iteration is completed by replacement of several edges in the cycle. In this case the cycle length either decreases or remains unchanged. A Hamiltonian cycle in the graph exists if its length is equal to zero (H = 0). Polynomial complexity of the algorithm results from the fact that the number of iterations for each unit edge of the cycle (i.e., when a correlation is made between the unit edges of the cycle and all zero edges of the graph) is finite. The algorithm makes it possible to find a minimal cycle in the graph, provided that any separate parts of the graph (if they exist) are connected by no less than three edges. (If parts of the graph are connected by two edges, then they are called weakly connected.) In these cases the completeness of the correlated edges holds, and a necessary prerequisite is created for rendering a proper decision, viz., the cycle is minimal or it may be enhanced. Testing with the use of other types of generators and codes showed that no errors in determining the minimal cycle were found for all the graphs where the connectivity requirements were met. At the same time, if these conditions were not satisfied for any particular graph, the completeness of the correlated edges was not always reached, resulting in the aforementioned errors.  
 
Testing also demonstrated that the polynomial characteristics of the algorithm do not depend on the type of graph and on its dimension (size). This is indicative of the versatility of the algorithm (US Patent No. 6,636,840 B11). The time required to determine the minimal cycle in the graph of a given dimension is essentially dependent on the following three factors: the initial cycle which is randomly specified; the existence of a cycle in the graph; and graph connectivity (vertex degree of the graph and the availability of weakly connected parts). The algorithm calculating time depends critically on the initial cycle in weakly connected graphs and can vary several dozen times for the same graph.  
 
The solution algorithm for the problem "Hamiltonian Cycle in a Graph" has an important distinctive feature when compared with the general "Traveling Salesman" problem. This lies in the fact that each graph has a preconcerted boundary value of the cycle H = 0, which enables one to leave the program at any stage of its work. However, it is known that a boundary of that kind does not exist in the "Traveling Salesman" problem. For this reason, in most cases the time required by this algorithm for determining the cycle itself differs essentially from the time taken to prove that the cycle does not exist. For most of the graph types the minimal cycle is determined much faster than (we can get) data on its non-existence.  
 
As an illustration, we can refer to the average (rated at 1000 tests) time for determining the minimal cycle. The results presented in the Table were obtained for 11 graphs taken from the well-known Internet library TSPLIB using a standard PC with an Intel Pentium M 1700 MHz processor, 1 MB Cache, 400 MHz Bus Clock, and 512 MB RAM, and controlled by OS Windows XP Pro.  
 
Table. Average (rated at 1000 tests) running times for determining a minimal cycle in various graphs  
#  
Name  
Type  
Average execution time  
Minimal cycle length  
1  
alb1000  
hcp  
0.72 sec  
H = 0  
2  
alb2000  
hcp  
3.29 sec  
H = 0  
3  
alb3000a  
hcp  
8.36 sec  
H = 0  
4  
alb3000b  
hcp  
8.02 sec  
H = 0  
5  
alb3000c  
hcp  
8.43 sec  
H = 0  
6  
alb3000d  
hcp  
8.48 sec  
H = 0  
7  
alb3000e  
hcp  
8.03 sec  
H = 0  
8  
alb4000  
hcp  
17.84 sec  
H = 0  
9  
alb5000  
hcp  
30.85 sec  
H = 0  
10  
leaper 7x8 on board 15x106  
hcp  
5.98 sec  
H = 0  
11  
leaper 6x7 on board 13x76  
hcp  
55.17 sec  
H > 0  
 
Site Map Contacts
Copyright © 1996-2017 International Intellectual Group, Inc.
About Efficiency TestLab Download / Purchase Support News
All rights reserved.