Research Report CS-RR-306

L.A. Goldberg and M. Jerrum, Randomly Sampling Molecules (June 1, 1996).

Abstract

We give the first polynomial-time algorithm for the following problem: Given a degree sequence in which each degree is bounded from above by a constant, select, uniformly at random, an unlabelled connected multigraph with the given degree sequence. We also give the first polynomial-time algorithm for the following related problem: Given a molecular formula, select, uniformly at random, a structural isomer having the giver formula.

Citation

This report has since been published elsewehere and is no longer available as a research report from Warwick. The published paper may be cited as:

L.A. Goldberg and M. Jerrum, "Randomly Sampling Molecules", Proceedings of 8th SODA, pp. 183-192 (1997)