Hill-climbing to Pasch valleys

Autor: Danny Heap, Eric Mendelsohn, Peter Danziger
Rok vydání: 2007
Předmět:
Zdroj: Journal of Combinatorial Designs. 15:405-419
ISSN: 1520-6610
1063-8539
DOI: 10.1002/jcd.20142
Popis: Exhaustive enumeration of Steiner Triple Systems is not feasible, due to the combinatorial explosion of instances. The next-best hope is to quickly find a sample that is representative of isomorphism classes. Stinson's Hill-Climbing algorithm [20] is widely used to produce random Steiner Triple Systems, and certainly finds a sample of systems quickly, but the sample is not uniformly distributed with respect to the isomorphism classes of STS with ν ≤ 19, and, in particular, we find that isomorphism classes with a large number of Pasch configurations are under-represented. No analysis of the non-uniformity of the distribution with respect to isomorphism classes or the intractability of obtaining a representative sample for ν > 19 is known. We also exhibit a modification to hill-climbing that makes the sample if finds closer to the uniform distribution over isomorphism classes in return for a modest increase in running time. © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 405–419, 2007
Databáze: OpenAIRE
Externí odkaz: