Expected Value of The Independence Number
by
Ying Zhang
University of Central Florida
Coauthors: Narsingh Deo (University of Central Florida)

Given the order (n) and size (m) of a connected graph G, estimating its independence number is an important problem, with practical as well as theoretical significance. This talk will first present a survey of known results; and then discuss our experimental methods and results on this topic. We work with the assumption that G is randomly chosen from all possible connected graphs of the given order and size. For small graphs, algorithms with implicit exhaustive enumeration can be used; but for larger graphs, since the independence number problem is NP-hard, we employ sampling method and study its fairness. Our experimental result shows that the variance of the independence number is surprisingly small.

Date received: April 20, 2001