Boltzmann Sampling of Unlabelled Structures

DOI10.1137/1.9781611972979.5zbMath1430.68164MaRDI QIDQ5194612

Éric Fusy, Carine Pivoteau, Philippe Flajolet

Publication date: 16 September 2019

Published in: 2007 Proceedings of the Fourth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611972979.5

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68R05: Combinatorics in computer science

68Q87: Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

Related Items

Counting, Generating, Analyzing and Sampling Tree Alignments, Unlabelled Gibbs partitions, Graph limits of random graphs from a subset of connected k‐trees, Distribution of variables in lambda-terms with restrictions on De Bruijn indices and De Bruijn levels, Generating constrained random data with uniform distribution, Counting and generating terms in the binary lambda calculus, Tuning as convex optimisation: a polynomial tuner for multi-parametric combinatorial samplers, Exact-Size Sampling of Enriched Trees in Linear Time, Graphon convergence of random cographs, Boltzmann samplers for \(v\)-balanced cycles, A new dichotomic algorithm for the uniform random generation of words in regular languages, Non-redundant random generation algorithms for weighted context-free grammars, Algorithms for combinatorial structures: well-founded systems and Newton iterations, Compact representations of all members of an independence system, Enumerations, forbidden subgraph characterizations, and the split-decomposition, Controlled non-uniform random generation of decomposable structures, Enumeration and random generation of accessible automata, The relevant prefixes of coloured Motzkin walks: an average case analysis, On the number of unary-binary tree-like structures with restrictions on the unary height, Boltzmann samplers for first-order differential specifications, On the lexicographical generation of compressed codes, Scaling limits of random Pólya trees, Uniform random posets, Recursive Combinatorial Structures: Enumeration, Probabilistic Analysis and Random Generation