Change search
ReferencesLink to record
Permanent link

Direct link
A SAT Based Effective Algorithm for the Directed Hamiltonian Cycle Problem
Computer Science Institute, Christian-Albrechts-University of Kiel, Germany .
Department of Computer Science/Department of Genetics, Washington University, United States .
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)
Abstract [en]

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
National Category
Discrete Mathematics
URN: urn:nbn:se:umu:diva-84450OAI: diva2:684156
5th International Computer Science Symposium in Russia (CSR 2010)
Available from: 2014-01-07 Created: 2014-01-07 Last updated: 2014-12-19Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Jäger, Gerold
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 16 hits
ReferencesLink to record
Permanent link

Direct link