Chinese Remainder Encoding for Hamiltonian Cycles
Chinese Remainder Encoding for Hamiltonian Cycles
复制标题
哈密顿循环的中文余数编码
DOI：
10.1007/978-3-030-80223-3_15
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Heule, Marijn J.H.
中科院分区：
文献类型：
--
作者：
Heule, Marijn J.H.
哈密顿圈问题(HCP)包含两个约束：i)每个顶点恰好为圈贡献两条边；ii)恰好存在一个圈。前者可以自然而紧凑地编码，而后者的编码要么缺乏弧线一致性，要么需要指数级的子句。基于中国剩余定理，我们提出了一种新的、较小的编码方式。我们在挑战HCP实例上演示了该编码的有效性。
The Hamiltonian Cycle Problem (HCP) consists of two constraints: i) each vertex contributes exactly two edges to the cycle; and ii) there is exactly one cycle. The former can be encoded naturally and compactly, while the encodings of the latter either lack arc consistency or require an exponential number of clauses. We present a new, small encoding for HCP based on the Chinese remainder theorem. We demonstrate the effectiveness of the encoding on challenging HCP instances.
登录
查看更多内容
危险 SAT 编码的形式化
DOI：
10.1007/978-3-540-72788-0_18
发表时间：
2007
期刊：
Fundam. Informaticae
影响因子：
--
作者：
Alexander Hertel;Philipp Hertel;A. Urquhart
通讯作者：
A. Urquhart
4 连通平面图的哈密顿循环问题是线性时间可解的
DOI：
10.1016/0196-6774(89)90012-6
发表时间：
1989
期刊：
J. Algorithms
影响因子：
--
作者：
Norishige Chiba;Takao Nishizeki
通讯作者：
Takao Nishizeki
答案集编程模非循环性
DOI：
10.3233/fi-2016-1398
发表时间：
2016
期刊：
Fundam. Informaticae
影响因子：
--
作者：
J. Bomanson;M. Gebser;T. Janhunen;B. Kaufmann;T. Schaub
通讯作者：
T. Schaub
用于排列问题绝对编码的高效 SAT 技术：在哈密顿循环中的应用
DOI：
--
发表时间：
2009
期刊：
Symposium on Abstraction, Reformulation and Approximation
影响因子：
--
作者：
M. Velev;Ping Gao
通讯作者：
Ping Gao
改变振铃和哈密顿循环：寻找艾琳和斯特德曼三元组
DOI：
10.5614/ejgta.2019.7.1.5
发表时间：
2017
期刊：
Electron. J. Graph Theory Appl.
影响因子：
--
作者：
M. Haythorpe;Andrew Johnson
通讯作者：
Andrew Johnson