|
Abstract : |
In this paper, we look at the problem of how one might try to hide a large independent set in a graph in which all other independent sets are significantly smaller. We observe that the most common methods of generating graphs with known maximum independent sets are subject to attack using simple techniques that are regularly successful on graphs of practical size. We present an improved random graph generation system, DELTA, which increases the range of maximum independent sets that can be hidden from these techniques. 1, |
