An Experimental Study on Hamiltonian Circuit of Random Graphs
Yisong Wang · Journal of Guizhou University · 2013
Hamilton Circuit is a typical NP-hard problem in graph theory.It is widely used as a test case to test the effectiveness of algorithms/systems,including Satisfiability(SAT),Answer Set Programming(ASP) and Constraint Satisfaction Problem(CSP),etc.In this paper,ASP solver clasp was used to study the existence,nonexistence,and hardness of evaluating Hamilton Circuit in random graphs,with a number of nodes between 40 and 100 nodes.The results show that they all have certain regularity.It is not only beneficial to explore Hamilton Circuit of random graphs,it also provides a useful guide to generate random graphs for benchmarks.