论文标题
汉密尔顿分解和验证销售人员多层室外1骨的顶点邻居搜索
Hamiltonian decomposition and verifying vertex adjacency in 1-skeleton of the traveling salesperson polytope by variable neighborhood search
论文作者
论文摘要
我们考虑将常规图表分为边缘偶发的哈密顿周期的哈密顿分解问题。在旅行销售员多层人群的1骨骨骼中，可以将其作为在4型多编码中的汉密尔顿分解问题的足够条件。我们为此问题介绍了一个启发式一般变量邻域搜索算法，以通过减少到完美的匹配和多个周期合并操作来找到多编码的顶点 - 局部循环盖。该算法有一个单方面的错误：答案“不相邻”总是正确的，并且在随机定向和无向的汉密尔顿周期和金字塔游览中进行了测试。
We consider a Hamiltonian decomposition problem of partitioning a regular graph into edge-disjoint Hamiltonian cycles. A sufficient condition for vertex adjacency in the 1-skeleton of the traveling salesperson polytope can be formulated as the Hamiltonian decomposition problem in a 4-regular multigraph. We introduce a heuristic general variable neighborhood search algorithm for this problem based on finding a vertex-disjoint cycle cover of the multigraph through reduction to perfect matching and several cycle merging operations. The algorithm has a one-sided error: the answer "not adjacent" is always correct, and was tested on random directed and undirected Hamiltonian cycles and on pyramidal tours.
