INDEPENDENT SETS IN RANDOM SPARSE GRAPHS

被引：20

作者：

GAZMURI, PG

机构：

[1] Univ Catolica de Chile, Dep, Ingenieria de Sistemas, Santiago,, Chile, Univ Catolica de Chile, Dep Ingenieria de Sistemas, Santiago, Chile

来源：

NETWORKS | 1984年 / 14卷 / 03期

关键词：

D O I：

10.1002/net.3230140302

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

The problem of finding maximum independent sets on sparse graphs is considered. A probabilistic analysis of this problem is presented, with the main objective being to obtain asymptotic lower and upper bounds on the size of the optimal solution. The results are extended to the case of random sparse hypergraphs, and bounds are obtained using similar methods. Finally, the case of Euclidean sparse graphs is considered. Simple asymptotically optimal strategies are presented for this model.

引用

页码：367 / 377

页数：11