Font Size: a A A

Better sampling of Steiner triple systems

Posted on:2006-05-20Degree:M.ScType:Thesis
University:University of Toronto (Canada)Candidate:Heap, DannyFull Text:PDF
GTID:2450390008460161Subject:Computer Science
Abstract/Summary:
Full enumeration of the Steiner Triple Systems on v points currently seems infeasible for v larger than 19, due to combinatorial explosion in the number of isomorphism classes. A reasonable alternative would be a technique for quickly finding a representative sample of STS(v)s, but existing techniques are either too slow (back-tracking), or find a sample that is not uniformly distributed with respect to STS instances (Stinson's hill-climbing algorithm). We investigate various modifications of hill-climbing to make the sample found closer to the uniform distribution over STS instances. We also consider a criterion for gauging how uniformly hill-climbing is sampling.
Keywords/Search Tags:STS
Related items