Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-08T14:34:22.901Z Has data issue: false hasContentIssue false

Boltzmann Samplers for the Random Generation of Combinatorial Structures

Published online by Cambridge University Press:  24 September 2004

PHILIPPE DUCHON
Affiliation:
LaBRI, Université de Bordeaux I, 351 Cours de la Libération, F-33405 Talence Cedex, France (e-mail: duchon@labri.fr)
PHILIPPE FLAJOLET
Affiliation:
Algorithms Project, INRIA-Rocquencourt, F-78153 Le Chesnay, France (e-mail: Philippe.Flajolet@inria.fr)
GUY LOUCHARD
Affiliation:
Université Libre de Bruxelles, Département d'informatique, Boulevard du Triomphe, B-1050 Bruxelles, Belgique (e-mail: louchard@ulb.ac.be)
GILLES SCHAEFFER
Affiliation:
Laboratoire d'Informatique (LIX), École Polytechnique, 91128 Palaiseau Cedex, France (e-mail: Gilles.Schaeffer@lix.polytechnique.fr)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

This article proposes a surprisingly simple framework for the random generation of combinatorial configurations based on what we call Boltzmann models. The idea is to perform random generation of possibly complex structured objects by placing an appropriate measure spread over the whole of a combinatorial class – an object receives a probability essentially proportional to an exponential of its size. As demonstrated here, the resulting algorithms based on real-arithmetic operations often operate in linear time. They can be implemented easily, be analysed mathematically with great precision, and, when suitably tuned, tend to be very efficient in practice.

Information

Type
Paper
Copyright
© 2004 Cambridge University Press