Random generation of combinatorial structures: Boltzmann samplers and beyond

Autor:	Duchon, Philippe
Rok vydání:	2011
Předmět:	Computer Science - Data Structures and Algorithms Mathematics - Combinatorics
Druh dokumentu:	Working Paper
Popis:	The Boltzmann model for the random generation of "decomposable" combinatorial structures is a set of techniques that allows for efficient random sampling algorithms for a large class of families of discrete objects. The usual requirement of sampling uniformly from the set of objects of a given size is somehow relaxed, though uniformity among objects of each size is still ensured. Generating functions, rather than the enumeration sequences they are based on, are the crucial ingredient. We give a brief description of the general theory, as well as a number of newer developments. Comment: Winter Simulation Conference (2011)
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1112.5071 Zobrazit plný text záznamu View this record from Arxiv