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