A SAT based effective algorithm for the directed Hamiltonian cycle problem

Gerold Jäger; Weixiong Zhang

doi:10.1007/978-3-642-13182-0_20

A SAT based effective algorithm for the directed Hamiltonian cycle problem

Gerold Jäger, Weixiong Zhang

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

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 effective 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 effective algorithms for the AP and SAT, our algorithm significantly outperforms previous exact DHCP algorithms including an algorithm based on the award-winning Concorde TSP algorithm.

Original language	English
Title of host publication	Computer Science - Theory and Applications - 5th International Computer Science Symposium in Russia, CSR 2010, Proceedings
Pages	216-227
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-13182-0_20
State	Published - 2010
Event	5th International Computer Science Symposium in Russia, CSR 2010 - Kazan, Russian Federation Duration: Jun 16 2010 → Jun 20 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6072 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	5th International Computer Science Symposium in Russia, CSR 2010
Country/Territory	Russian Federation
City	Kazan
Period	06/16/10 → 06/20/10

Access to Document

10.1007/978-3-642-13182-0_20

Cite this

Jäger, G., & Zhang, W. (2010). A SAT based effective algorithm for the directed Hamiltonian cycle problem. In Computer Science - Theory and Applications - 5th International Computer Science Symposium in Russia, CSR 2010, Proceedings (pp. 216-227). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6072 LNCS). https://doi.org/10.1007/978-3-642-13182-0_20

Jäger, Gerold ; Zhang, Weixiong. / A SAT based effective algorithm for the directed Hamiltonian cycle problem. Computer Science - Theory and Applications - 5th International Computer Science Symposium in Russia, CSR 2010, Proceedings. 2010. pp. 216-227 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{88ea9d5ff5604c91802d9f5bcf0bd58f,

title = "A SAT based effective algorithm for the directed Hamiltonian cycle problem",

abstract = "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 effective 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 effective algorithms for the AP and SAT, our algorithm significantly outperforms previous exact DHCP algorithms including an algorithm based on the award-winning Concorde TSP algorithm.",

author = "Gerold J{\"a}ger and Weixiong Zhang",

year = "2010",

doi = "10.1007/978-3-642-13182-0_20",

language = "English",

isbn = "3642131816",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "216--227",

booktitle = "Computer Science - Theory and Applications - 5th International Computer Science Symposium in Russia, CSR 2010, Proceedings",

note = "5th International Computer Science Symposium in Russia, CSR 2010 ; Conference date: 16-06-2010 Through 20-06-2010",

}

Jäger, G & Zhang, W 2010, A SAT based effective algorithm for the directed Hamiltonian cycle problem. in Computer Science - Theory and Applications - 5th International Computer Science Symposium in Russia, CSR 2010, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6072 LNCS, pp. 216-227, 5th International Computer Science Symposium in Russia, CSR 2010, Kazan, Russian Federation, 06/16/10. https://doi.org/10.1007/978-3-642-13182-0_20

A SAT based effective algorithm for the directed Hamiltonian cycle problem. / Jäger, Gerold; Zhang, Weixiong.
Computer Science - Theory and Applications - 5th International Computer Science Symposium in Russia, CSR 2010, Proceedings. 2010. p. 216-227 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6072 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A SAT based effective algorithm for the directed Hamiltonian cycle problem

AU - Jäger, Gerold

AU - Zhang, Weixiong

PY - 2010

Y1 - 2010

N2 - 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 effective 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 effective algorithms for the AP and SAT, our algorithm significantly outperforms previous exact DHCP algorithms including an algorithm based on the award-winning Concorde TSP algorithm.

AB - 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 effective 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 effective algorithms for the AP and SAT, our algorithm significantly outperforms previous exact DHCP algorithms including an algorithm based on the award-winning Concorde TSP algorithm.

UR - http://www.scopus.com/inward/record.url?scp=77954574327&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-13182-0_20

DO - 10.1007/978-3-642-13182-0_20

M3 - Conference contribution

AN - SCOPUS:77954574327

SN - 3642131816

SN - 9783642131813

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 216

EP - 227

BT - Computer Science - Theory and Applications - 5th International Computer Science Symposium in Russia, CSR 2010, Proceedings

T2 - 5th International Computer Science Symposium in Russia, CSR 2010

Y2 - 16 June 2010 through 20 June 2010

ER -

Jäger G, Zhang W. A SAT based effective algorithm for the directed Hamiltonian cycle problem. In Computer Science - Theory and Applications - 5th International Computer Science Symposium in Russia, CSR 2010, Proceedings. 2010. p. 216-227. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-13182-0_20

A SAT based effective algorithm for the directed Hamiltonian cycle problem

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this