Fast probabilistic algorithms for hamiltonian circuits and matchings
Fast probabilistic algorithms for hamiltonian circuits and matchings
复制标题
DOI：
10.1145/800105.803393
复制
发表时间：
1977-05
期刊：
影响因子：
--
通讯作者：
D. Angluin;L. Valiant
中科院分区：
文献类型：
--
作者：
D. Angluin;L. Valiant
本文的主要目的是给技术分析的概率性能的某些种类的算法，从而提出一些快速算法与可证明的理想的概率行为。我们考虑的具体问题是：在有向图（DHC）中找到哈密顿回路，在无向图（UHC）中找到哈密顿回路，以及在无向图（PM）中找到完美匹配。我们发现，对于每个问题都有一个算法，是非常快的（0（n（log n）2）DHC和UHC，和0（nlog n）PM），并与概率趋于一个找到一个解决方案，在随机选择的图形足够的密度。这些结果与前两个问题[2，12]的已知NP-完全性和最后一个问题[9]的最佳最坏情况上限0（n2.5）形成对比。
The main purpose of this paper is to give techniques for analysing the probabilistic performance of certain kinds of algorithms, and hence to suggest some fast algorithms with provably desirable probabilistic behaviour. The particular problems we consider are: finding Hamiltonian circuits in directed graphs (DHC), finding Hamiltonian circuits in undirected graphs (UHC), and finding perfect matchings in undirected graphs (PM). We show that for each problem there is an algorithm that is extremely fast (0(n(log n)2) for DHC and UHC, and 0(nlog n) for PM), and which with probability tending to one finds a solution in randomly chosen graphs of sufficient density. These results contrast with the known NP-completeness of the first two problems [2,12] and the best worst-case upper bound known of 0(n2.5) for the last [9].