ON THE INDEPENDENCE NUMBER OF RANDOM CUBIC GRAPHS

被引：20

作者：

FRIEZE, A

SUEN, S

机构：

[1] Department of Mathematics, Carnegie Mellon University, Pittsburgh, Pennsylvania

来源：

RANDOM STRUCTURES & ALGORITHMS | 1994年 / 5卷 / 05期

关键词：

D O I：

10.1002/rsa.3240050504

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We show that as n --> infinity, the independence number alpha(G), for almost all 3-regular graphs G on n vertices, is at least (6 log(3/2) - 2 - epsilon)n, for any constant epsilon > 0. We prove this by analyzing a greedy algorithm for finding independent sets. (C) 1994 John Wiley & Sons, Inc.

引用

页码：649 / 664

页数：16