论文标题
计算第二个哈密顿周期的精确和近似算法
Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle
论文作者
论文摘要
在本文中，我们考虑以下总功能问题：鉴于立方汉密尔顿图$ g $和一个hamiltonian循环$ c_0 $ $ g $，我们如何计算第二个汉密尔顿周期$ C_1 \ neq C_0 $ $ g $？塞德里克·史密斯（Cedric Smith）在1946年使用非建设性平价论点证明，这是第二个汉密尔顿周期总是存在的。我们的主要结果是一种算法，该算法计算时间$ o（n \ cdot 2^{（（0.3- \ varepsilon）n}）n}）$时间，对于某些积极的常数$ \ varepsilon> 0 $，以及在多项式空间中，从而改善了解决此问题的途径。我们的算法基于Thomason Lollipop算法的基本结构特性，我们在这里首次证明了这一点。在近似于哈密顿图$ g $中的第二个周期的长度的方向上，给定的哈密顿量周期$ C_0 $（我们可能无法保证存在第二个哈密顿量周期的存在），我们提供的线性算法以至少长度为$ n -4α（\ sqrt）（\ sqrt plengive of第二周期） \ frac {δ-2} {δ-2} $和$δ，δ$分别是图的最小值和最大程度。这种近似结果也改善了艺术的状态。
In this paper we consider the following total functional problem: Given a cubic Hamiltonian graph $G$ and a Hamiltonian cycle $C_0$ of $G$, how can we compute a second Hamiltonian cycle $C_1 \neq C_0$ of $G$? Cedric Smith proved in 1946, using a non-constructive parity argument, that such a second Hamiltonian cycle always exists. Our main result is an algorithm which computes the second Hamiltonian cycle in time $O(n \cdot 2^{(0.3-\varepsilon)n})$ time, for some positive constant $\varepsilon>0$, and in polynomial space, thus improving the state of the art running time for solving this problem. Our algorithm is based on a fundamental structural property of Thomason's lollipop algorithm, which we prove here for the first time. In the direction of approximating the length of a second cycle in a Hamiltonian graph $G$ with a given Hamiltonian cycle $C_0$ (where we may not have guarantees on the existence of a second Hamiltonian cycle), we provide a linear-time algorithm computing a second cycle with length at least $n - 4α(\sqrt{n}+2α)+8$, where $α= \frac{Δ-2}{δ-2}$ and $δ,Δ$ are the minimum and the maximum degree of the graph, respectively. This approximation result also improves the state of the art.
