A SAT Based Effective Algorithm for the Directed Hamiltonian Cycle Problem

1. Angluin, D., Valiant, L.G.: Fast Probabilistic Algorithms for Hamiltonian Circuits and Matchings. J. Comput. System. Sci. 18(2), 155–193 (1979)

   Article  MATH  MathSciNet  Google Scholar 

2. Applegate, D.L., Bixby, R.E., Chvátal, V., Cook, W.J.: The Traveling Salesman Problem. A Computational Study. Princeton University Press, Princeton (2006)

   MATH  Google Scholar 

3. Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms and Applications, ch. 5. Springer, London (2008), http://www.cs.rhul.ac.uk/books/dbook/

   Google Scholar 

4. Bollobás, B., Fenner, T.I., Frieze, A.M.: An Algorithm for Finding Hamiltonian Paths and Cycles in Random Graphs. Combinatorica 7(4), 327–341 (1987)

   Article  MATH  MathSciNet  Google Scholar 

5. Christofides, N.: Graph Theory – An Algorithmic Approach. Academic Press, New York (1975)

   MATH  Google Scholar 

6. Chvátal, V.: Hamiltonian Cycles. In: Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B. (eds.) The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimization, ch. 11. John Wiley & Sons, Chichester (1985)

   Google Scholar 

7. Eén, N., Sörensson, N.: An Extensible SAT-Solver. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol. 2919, pp. 502–518. Springer, Heidelberg (2004)

   Google Scholar 

8. Frieze, A.M.: Finding Hamiltonian Cycles in Sparse Random Graphs. J. Combin. Theory Ser. B 44, 230–250 (1988)

   Article  MATH  MathSciNet  Google Scholar 

9. Frieze, A.M.: An Algorithm for Finding Hamilton Cycles in Random Directed Graphs. J. Algorithms 9, 181–204 (1988)

   Article  MATH  MathSciNet  Google Scholar 

10. Frieze, A.M., Suen, S.: Counting Hamilton cycles in random directed graphs. Random Structures Algorithms 9, 235–242 (1992)

    Article  MathSciNet  Google Scholar 

11. Glover, F., Gutin, G., Yeo, A., Zverovich, A.: Construction Heuristics for the Asymmetric TSP. European J. Oper. Res. 129, 555–568 (2001)

    Article  MATH  MathSciNet  Google Scholar 

12. Goldengorin, B., Jäger, G., Molitor, P.: Tolerance Based Contract-or-Patch Heuristic for the Asymmetric TSP. In: Erlebach, T. (ed.) CAAN 2006. LNCS, vol. 4235, pp. 86–97. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

13. Gould, R.J.: Updating the Hamiltonian Problem – a Survey. J. Graph Theory 15(2), 121–157 (1991)

    Article  MATH  MathSciNet  Google Scholar 

14. Grebinski, V., Kucherov, G.: Reconstructing a Hamiltonian Circuit by Querying the Graph: Application to DNA Physical Mapping. IR 96-R-123, Centre de Recherche en Informatique de Nancy (1996)

    Google Scholar 

15. Henderson, R., Apodaca, E.: A Knight of Egodeth: Zen Raptured Quietude. Book Surge Publishing (2008)

    Google Scholar 

16. Jin, H., Han, H., Somenzi, F.: Efficient Conflict Analysis for Finding All Satisfying Assignments of a Boolean Circuit. In: Halbwachs, N., Zuck, L.D. (eds.) TACAS 2005. LNCS, vol. 3440, pp. 287–300. Springer, Heidelberg (2005)

    Google Scholar 

17. Johnson, D.S., Gutin, G., McGeoch, L.A., Yeo, A., Zhang, W., Zverovich, A.: Experimental Analysis of Heuristics for the ATSP. In: Gutin, G., Punnen, A.P. (eds.) The Traveling Salesman Problem and Its Variations, ch. 10. Kluwer, Dordrecht (2002)

    Google Scholar 

18. Jonker, R., Volgenant, A.: Transforming Asymmetric into Symmetric Traveling Salesman Problems. Oper. Res. Lett. 2(4), 161–163 (1983)

    Article  MATH  Google Scholar 

19. Jonker, R., Volgenant, A.: A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems. Computing 38, 325–340 (1987)

    Article  MATH  MathSciNet  Google Scholar 

20. Karp, R.M.: Reducibility Among Combinatorial Problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum, New York (1972)

    Google Scholar 

21. Karp, R.M., Steele, J.M.: Probabilistic Analysis of Heuristics. In: Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B. (eds.) The Traveling Salesman Problem. A Guided Tour of Combinatorial Optimization, ch. 6. John Wiley & Sons, Chicester (1985)

    Google Scholar 

22. Kelly, L.: Hamilton Cycles in Directed Graphs. PhD Thesis, University of Birmingham, United Kingdom (2007)

    Google Scholar 

23. Komlós, M., Szemerédi, E.: Limit Distribution for the Existence of a Hamiltonian Cycle in a Random Graph. Discrete Math. 43, 55–63 (1983)

    Article  MATH  MathSciNet  Google Scholar 

24. Kyek, O., Parberry, I., Wegener, I.: Bounds on the Number of Knight’s Tours. Discrete Appl. Math. 74(2), 171–181 (1997)

    Article  MATH  MathSciNet  Google Scholar 

25. Lynce, I., Marques-Silva, J.: Efficient Haplotype Inference with Boolean Satisfiability. In: Proc. 21st National Conference on Artificial Intelligence (AAAI). AAAI Press, Menlo Park (2006)

    Google Scholar 

26. Martello, S.: An Enumerative Algorithm for Finding Hamiltonian Circuits in a Directed Graph. ACM Trans. Math. Software 9(1), 131–138 (1983)

    Article  MATH  MathSciNet  Google Scholar 

27. McDiarmid, C.J.H.: Cluster Percolation and Random Graphs. Math. Program. Stud. 13, 17–25 (1980)

    MATH  MathSciNet  Google Scholar 

28. Pósa, L.: Hamiltonian Circuits in Random Graphs. Discrete Math. 14, 359–364 (1976)

    Article  MATH  MathSciNet  Google Scholar 

29. Stojaković, M., Szabó, T.: Positional Games on Random Graphs. Random Structures Algorithms 26(1-2), 204–223 (2005)

    Article  MATH  MathSciNet  Google Scholar 

30. Vandegriend, B.: Finding Hamiltonian Cycles: Algorithms, Graphs and Performance. Master Thesis, University of Alberta, Canada (1998)

    Google Scholar 

31. 8th DIMACS Implementation Challenge: The Traveling Salesman Problem, http://www.research.att.com/~dsj/chtsp/

32. The Hamiltonian Page by Gutin, G., Moscato, P.: http://www.ing.unlp.edu.ar/cetad/mos/Hamilton.html

33. The Stony Brook Algorithm Repository by Skiena, S.: http://www.cs.sunysb.edu/~algorith/files/hamiltonian-cycle.shtml

34. Source code of [2](Concorde), http://www.tsp.gatech.edu/concorde.html

35. Source code of [7] (MiniSat), http://minisat.se

36. Source code of [19], http://www.magiclogic.com/assignment.html

Download references