A SAT Based Effective Algorithm for the Directed Hamiltonian Cycle Problem
2010 (English)In: Proceedings of 5th International Computer Science Symposium in Russia (CSR 2010) / [ed] F. Ablayev and E.W. Mayr, Berlin-Heidelberg: Springer Berlin-Heidelberg , 2010, 216-227 p.Conference paper (Refereed)
The Hamiltonian cycle problem (HCP) is an important combinatorial problem with applications in many areas. While thorough theoretical and experimental analyses have been made on the HCP in undirected graphs, little is known for the HCP in directed graphs (DHCP). The contribution of this work is an e ective algorithm for the DHCP. Our algorithm explores and exploits the close relationship between the DHCP and the Assignment Problem (AP) and utilizes a technique based on Boolean satisfiability (SAT). By combining e ective algorithms for the AP and SAT, our algorithm signicantly outperforms previous exact DHCP algorithms including an algorithm based on the award-winning Concorde TSP algorithm.
Place, publisher, year, edition, pages
Berlin-Heidelberg: Springer Berlin-Heidelberg , 2010. 216-227 p.
, Lecture Notes in Computer Science, Volume 6072
IdentifiersURN: urn:nbn:se:umu:diva-84450OAI: oai:DiVA.org:umu-84450DiVA: diva2:684156
5th International Computer Science Symposium in Russia (CSR 2010)