Premium
Independent sets in random sparse graphs
Author(s) -
Gazmuri Pedro G.
Publication year - 1984
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230140302
Subject(s) - mathematics , combinatorics , simple (philosophy) , random graph , asymptotically optimal algorithm , euclidean geometry , upper and lower bounds , discrete mathematics , probabilistic logic , graph , dense graph , mathematical optimization , line graph , pathwidth , statistics , philosophy , mathematical analysis , geometry , epistemology
We consider the problem of finding maximum independent sets on sparse graphs. 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. If we let n be the number of nodes in the graph, we show that with probability tending to 1 as n /rightarrow /infty, this size lies between [ D 1 n ] and [ D 2 n ], where D 1 and D 2 are specific functions of the average degree of a node. The lower bound is obtained by examining the behavior of a simple algorithm for constructing independent sets. We then extend our results to the case of random sparse hypergraphs and obtain bounds using similar methods. Finally, we consider the case of Euclidean sparse graphs. Simple asymptotically optimal strategies are presented for this model.