An Effective Algorithm for and Phase Transitions of the Directed Hamiltonian Cycle Problem

DOI10.1613/jair.3109zbMath1210.68074arXiv1401.3863OpenAlexW2164243805WikidataQ129499997 ScholiaQ129499997MaRDI QIDQ3067705

Gerold Jäger, Weixiong Zhang

Publication date: 21 January 2011

Published in: Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1401.3863

zbMATH Keywords

combinatorial problemsHamiltonian cycle problem (HCP)HCP in directed graphs (DHCP)

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

The complete parsimony haplotype inference problem and algorithms based on integer programming, branch-and-bound and Boolean satisfiability ⋮ Incremental SAT-Based Method with Native Boolean Cardinality Handling for the Hamiltonian Cycle Problem ⋮ Empirical Study of Phase Transition of Hamiltonian Cycle Problem in Random Graphs with Degrees Greater Than One ⋮ SAT and IP based algorithms for magic labeling including a complete search for total magic labelings

Uses Software

• Concorde

This page was built for publication: An Effective Algorithm for and Phase Transitions of the Directed Hamiltonian Cycle Problem