umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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, Published 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.
Series
Lecture Notes in Computer Science, Volume 6072
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-84450OAI: oai:DiVA.org:umu-84450DiVA: diva2:684156
Conference
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

urn-nbn

Altmetric score

urn-nbn
Total: 45 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf