论文标题
为K-Unbound Hamiltonian周期找到一个下限
Finding a Lower Bound for k-Unbounded Hamiltonian Cycles
论文作者
论文摘要
已经广泛研究了图表中哈密顿周期存在的方法。但是，在不存在哈密顿周期的情况下，几乎没有进行研究。如果顶点在路径中多次访问，请“无限”。此外，让一个Kunbound的Hamiltonian循环是一条有限长度的路径，访问每个顶点，具有相邻的启动和结束顶点，并包含K无基础的顶点。我们考虑了汉密尔顿周期问题的一种新型变体，其中目的是找到一个无数的汉密尔顿循环，其中m是K的最小值，以使K-unabound the the khonbound hamiltonian循环存在。我们首先考虑在著名的非哈米尔顿图上的任务。然后，我们为确定汉密尔顿杂志周期的M级蛮算法算法提供了指数时间的蛮力算法，并讨论了通过转换到汉密尔顿周期问题和不对称旅行推销员问题来解决变体的方法。最后，我们提出了一个多项式时间启发式方法，用于确定一个无数的汉密尔顿周期，这也被证明是原始的汉密尔顿周期问题的有效启发式。
Methods to determine the existence of Hamiltonian Cycles in graphs have been extensively studied. However, little research has been done following cases when no Hamiltonian Cycle exists. Let a vertex be "unbounded" if it is visited more than once in a path. Furthermore, let a k-Unbounded Hamiltonian Cycle be a path with finite length that visits every vertex, has adjacent start and end vertices, and contains k unbounded vertices. We consider a novel variant of the Hamiltonian Cycle Problem in which the objective is to find an m-Unbounded Hamiltonian Cycle where m is the minimum value of k such that a k-Unbounded Hamiltonian Cycle exists. We first consider the task on well-known non-Hamiltonian graphs. We then provide an exponential-time brute-force algorithm for the determination of an m-Unbounded Hamiltonian Cycle and discuss approaches to solve the variant through transformations to the Hamiltonian Cycle Problem and the Asymmetric Traveling Salesman Problem. Finally, we present a polynomial-time heuristic for the determination of an m-Unbounded Hamiltonian Cycle that is also shown to be an effective heuristic for the original Hamiltonian Cycle Problem.
