We present CertifyHAM, an algorithm which takes as input a graph G and either finds a Hamilton cycle of G or it outputs that such a cycle does not exists. If G=G(n, p) and p >2000/n then the expected running time of CertifyHAM is O(n/p). This improves upon previous results due to Gurevich and Shelah, Thomason and Alon and Krivelevich.
翻译：我们提出“认证”HAM,这是一种算法,以图G作为输入,或者发现汉密尔顿G周期,或者发现汉密尔顿G周期不存在。如果G=G(n, p)和p>2000/n,那么“认证HAM”的预期运行时间是O(n/p)。由于Gurevich和Shelah、Thomason、Alon和Krivelevich的缘故,这一算法比以前的结果有所改善。
相关内容
FAST：Conference on File and Storage Technologies。
Explanation：文件和存储技术会议。
Publisher：USENIX。
SIT:http://dblp.uni-trier.de/db/conf/fast/
Arxiv
0+阅读 · 2022年1月28日
Arxiv
0+阅读 · 2022年1月28日
相关VIP内容
相关资讯
相关论文
Arxiv
0+阅读 · 2022年1月28日
Arxiv
0+阅读 · 2022年1月28日
微信扫码咨询专知VIP会员