<%@ page language="java" contentType="text/html" %> <%-- Include common initialisation code --%> <%@ include file="/arch/common.jsp" %> <%-- The current tab --%> <% String currentTab = "Research"; %> <%-- Content of navigation pane --%> <%@ include file="nav.jsp" %> <% showCurrentLink=true; %> <%-- Current navigation location --%> <% String currentNav = "Reports and Theses"; %> <%-- Include the code for the document header --%> <%@ include file="/arch/header.jsp" %>

Research Report CS-RR-306

<%-- Include the code for the lines and navigation --%> <%@ include file="/arch/middle.jsp" %>

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.

<%@ include file="cited.html" %>

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

<%-- Include the code for the document footer --%> <%@ include file="/arch/footer.jsp" %>