文章基本信息

标题：An O(N) Time Algorithm for Finding Hamilton Cycles with High Probability
本地全文：下载
作者：Rajko Nenadov ; Angelika Steger ; Pascal Su 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：185
页码：60:1-60:17
DOI：10.4230/LIPIcs.ITCS.2021.60
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We design a randomized algorithm that finds a Hamilton cycle in ð'ª(n) time with high probability in a random graph G_{n,p} with edge probability p â¥ C log n / n. This closes a gap left open in a seminal paper by Angluin and Valiant from 1979.
关键词：Random Graphs; Hamilton Cycle; Perfect Matching; Linear Time; Sublinear Algorithm; Random Walk; Coupon Collector