How many random edges make a dense graph hamiltonian?

被引：72

作者：

Bohman, T ^{[1
]}

Frieze, A ^{[1
]}

Martin, R ^{[1
]}

机构：

[1] Carnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15213 USA

来源：

RANDOM STRUCTURES & ALGORITHMS | 2003年 / 22卷 / 01期

关键词：

D O I：

10.1002/rsa.10070

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

This paper investigates the number of random edges required to add to an arbitrary dense graph in order to make the resulting graph hamiltonian with high probability. Adding Theta(n) random edges is both necessary and sufficient to ensure this for all such dense graphs. If, however, the original graph contains no large independent set, then many fewer random edges are required. We prove a similar result for directed graphs. (C) 2002 Wiley Periodicals, Inc.

引用

页码：33 / 42

页数：10