Boltzmann Samplers for the Random Generation of Combinatorial Structures
From MaRDI portal
Publication:4670356
DOI10.1017/S0963548304006315zbMath1081.65007WikidataQ56032706 ScholiaQ56032706MaRDI QIDQ4670356
Philippe Duchon, Gilles Schaeffer, Philippe Flajolet, Guy Louchard
Publication date: 18 April 2005
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1017/s0963548304006315
65C10: Random number generation in numerical analysis
Related Items
Random generation of closed simply typed λ-terms: A synergy between logic programming and Boltzmann samplers, Counting, Generating, Analyzing and Sampling Tree Alignments, Unnamed Item, Unnamed Item, Unnamed Item, Unlabelled Gibbs partitions, On the enumeration of closures and environments with an application to random generation, Finite Automata, Probabilistic Method, and Occurrence Enumeration of a Pattern in Words and Permutations, Random Generation of Deterministic Acyclic Automata Using Markov Chains, 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, Formulae and Asymptotics for Coefficients of Algebraic Functions, Probabilistic Divide-and-Conquer: A New Exact Simulation Method, With Integer Partitions as an Example, Counting and generating terms in the binary lambda calculus, Normal-order reduction grammars, Unnamed Item, Spectral Experiments+, 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, Random cographs: Brownian graphon limit and asymptotic degree distribution, On the largest part size of low‐rank combinatorial assemblies, Models of random subtrees of a graph, Asymptotic expansions relating to the distribution of the length of longest increasing subsequences, Topological language for RNA, 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, Asymptotics and random sampling for BCI and BCK lambda terms, Analytic combinatorics of chord and hyperchord diagrams with \(k\) crossings, Sampling different kinds of acyclic automata using Markov chains, Algorithms for combinatorial structures: well-founded systems and Newton iterations, Crossings and nestings for arc-coloured permutations and automation, Fatgraph models of RNA structure, An algorithm computing combinatorial specifications of permutation classes, Weakly directed self-avoiding walks, On properties of random dissections and triangulations, Enumerations, forbidden subgraph characterizations, and the split-decomposition, Controlled non-uniform random generation of decomposable structures, Counting and generating permutations in regular classes, Random sampling of contingency tables via probabilistic divide-and-conquer, Shapes of topological RNA structures, Families of prudent self-avoiding walks, Enumeration and random generation of accessible automata, Stacks in canonical RNA pseudoknot structures, The relevant prefixes of coloured Motzkin walks: an average case analysis, Exact sampling algorithms for Latin squares and Sudoku matrices via probabilistic divide-and-conquer, Improvements to exact Boltzmann sampling using probabilistic divide-and-conquer and the recursive method, Symmetries of unlabelled planar triangulations, Enumerating lambda terms by weighted length of their de Bruijn representation, On the number of unary-binary tree-like structures with restrictions on the unary height, Boltzmann samplers for first-order differential specifications, Synchronization of Bernoulli sequences on shared letters, Exhaustive generation of some lattice paths and their prefixes, On the dependence of the component counting process of a uniform random variable, Statistics for unimodal sequences, Scaling limits of permutation classes with a finite specification: a dichotomy, Threshold functions for small subgraphs in simple graphs and multigraphs, Limits of random tree-like discrete structures, Universal limits of substitution-closed permutation classes, Counting phylogenetic networks of level 1 and 2, Partitions into distinct parts with bounded largest part, Incremental delay enumeration: space and time, Statistical properties of lambda terms, On RNA-RNA interaction structures of fixed topological genus, Polyhedral omega: a new algorithm for solving linear Diophantine systems, Generating labeled planar graphs uniformly at random, Efficient random sampling of binary and unary-binary trees via holonomic equations, Probabilistic divide-and-conquer: deterministic second half, A linear algorithm for the random sampling from regular languages, Generation of RNA pseudoknot structures with topological genus filtration, Enumeration and generation with a string automata representation, Uniform random posets, RNA secondary structures with given motif specification: combinatorics and algorithms, Random-Bit Optimal Uniform Sampling for Rooted Planar Trees with Given Sequence of Degrees and Applications, Boltzmann sampling of ordered structures, Vertices of Degree k in Random Unlabeled Trees, AVERAGE-CASE ANALYSIS OF PERFECT SORTING BY REVERSALS, Random Deterministic Automata, The maximum degree of random planar graphs, Polynomial Functors Constrained by Regular Expressions, Uniform Generation in Trace Monoids, Random Generation and Enumeration of Accessible Deterministic Real-Time Pushdown Automata, 3-Connected Cores In Random Planar Graphs, An Experimental Study on Generating Planar Graphs, Uniform random sampling of planar graphs in linear time, Random unlabelled graphs containing few disjoint cycles, Random k -noncrossing RNA structures, Vertices of degree k in random unlabeled trees, Asymptotic Properties of Some Minor-Closed Classes of Graphs, Recursive Combinatorial Structures: Enumeration, Probabilistic Analysis and Random Generation, RANDOM GENERATION OF FINITELY GENERATED SUBGROUPS OF A FREE GROUP, The Degree Sequence of Random Graphs from Subcritical Classes, Random Sampling of Plane Partitions
Uses Software