论文标题
回溯算法，用于构建4型多编码的哈密顿分解
Backtracking algorithms for constructing the Hamiltonian decomposition of a 4-regular multigraph
论文作者
论文摘要
我们考虑将常规图表分为边缘偶发的哈密顿周期的哈密顿分解问题。众所周知，在对称和不对称旅行销售人员多面体的1个骨骼中验证顶点非ja骨是NP完整的。另一方面，可以将两个顶点不贴为不变的足够条件作为组合问题，即在4个规范的多编码中找到第二个哈密顿分解。我们提出了两种回溯算法，用于构建第二个哈密顿分解并验证顶点非附录：基于简单路径扩展的算法和基于链边缘固定过程的算法。 基于无方向性的计算实验的结果，这两种算法都失去了已知的通用变量邻里搜索启发式方法。但是，对于有向的多编码，基于边缘链固定的算法显示，结果与现有解决方案的实例相当，并且在不存在的Hamiltonian分解的实例上更好地结果。
We consider a Hamiltonian decomposition problem of partitioning a regular graph into edge-disjoint Hamiltonian cycles. It is known that verifying vertex non-adjacency in the 1-skeleton of the symmetric and asymmetric traveling salesperson polytopes is NP-complete. On the other hand, a sufficient condition for two vertices to be non-adjacent can be formulated as a combinatorial problem of finding a second Hamiltonian decomposition of a 4-regular multigraph. We present two backtracking algorithms for constructing a second Hamiltonian decomposition and verifying vertex non-adjacency: an algorithm based on a simple path extension and an algorithm based on the chain edge fixing procedure. Based on the results of computational experiments for undirected multigraphs, both backtracking algorithms lost to the known general variable neighborhood search heuristics. However, for directed multigraphs, the algorithm based on chain fixing of edges showed results comparable to heuristics on instances with an existing solution and better results on infeasible instances where the Hamiltonian decomposition does not exist.
