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 levelsTuning as convex optimisation: a polynomial tuner for multi-parametric combinatorial samplersPolyhedral omega: a new algorithm for solving linear Diophantine systemsAVERAGE-CASE ANALYSIS OF PERFECT SORTING BY REVERSALSStatistics for unimodal sequencesGenerating labeled planar graphs uniformly at randomOn the enumeration of closures and environments with an application to random generationScaling limits of permutation classes with a finite specification: a dichotomyAsymptotic Properties of Some Minor-Closed Classes of GraphsRandom Deterministic AutomataTopological language for RNAThe maximum degree of random planar graphsEfficient random sampling of binary and unary-binary trees via holonomic equationsUniform random posetsProbabilistic divide-and-conquer: deterministic second halfPolynomial Functors Constrained by Regular ExpressionsRecursive Combinatorial Structures: Enumeration, Probabilistic Analysis and Random GenerationExact sampling algorithms for Latin squares and Sudoku matrices via probabilistic divide-and-conquerUniform Generation in Trace MonoidsBoltzmann samplers for \(v\)-balanced cyclesA new dichotomic algorithm for the uniform random generation of words in regular languagesNon-redundant random generation algorithms for weighted context-free grammarsAsymptotics and random sampling for BCI and BCK lambda termsRandom Generation and Enumeration of Accessible Deterministic Real-Time Pushdown AutomataExact-Size Sampling of Enriched Trees in Linear TimeImprovements to exact Boltzmann sampling using probabilistic divide-and-conquer and the recursive methodUnnamed ItemAnalytic combinatorics of chord and hyperchord diagrams with \(k\) crossingsThreshold functions for small subgraphs in simple graphs and multigraphsGraphon convergence of random cographsRandom cographs: Brownian graphon limit and asymptotic degree distributionOn the largest part size of low‐rank combinatorial assembliesFinite Automata, Probabilistic Method, and Occurrence Enumeration of a Pattern in Words and PermutationsLimits of random tree-like discrete structuresShapes of topological RNA structuresRNA secondary structures with given motif specification: combinatorics and algorithmsA linear algorithm for the random sampling from regular languagesModels of random subtrees of a graphAsymptotic expansions relating to the distribution of the length of longest increasing subsequencesRandom generation of closed simply typed λ-terms: A synergy between logic programming and Boltzmann samplersSymmetries of unlabelled planar triangulationsFormulae and Asymptotics for Coefficients of Algebraic FunctionsProbabilistic Divide-and-Conquer: A New Exact Simulation Method, With Integer Partitions as an ExampleRANDOM GENERATION OF FINITELY GENERATED SUBGROUPS OF A FREE GROUPEnumerating lambda terms by weighted length of their de Bruijn representationGeneration of RNA pseudoknot structures with topological genus filtrationSampling different kinds of acyclic automata using Markov chainsWeakly directed self-avoiding walksCounting and generating terms in the binary lambda calculusNormal-order reduction grammarsAlgorithms for combinatorial structures: well-founded systems and Newton iterationsUniversal limits of substitution-closed permutation classesCounting phylogenetic networks of level 1 and 2On properties of random dissections and triangulationsPartitions into distinct parts with bounded largest part3-Connected Cores In Random Planar GraphsCrossings and nestings for arc-coloured permutations and automationThe Degree Sequence of Random Graphs from Subcritical ClassesEnumerations, forbidden subgraph characterizations, and the split-decompositionAn Experimental Study on Generating Planar GraphsEnumeration and generation with a string automata representationRandom Sampling of Plane PartitionsOn the number of unary-binary tree-like structures with restrictions on the unary heightFatgraph models of RNA structureAn algorithm computing combinatorial specifications of permutation classesBoltzmann samplers for first-order differential specificationsFamilies of prudent self-avoiding walksSpectral Experiments+Synchronization of Bernoulli sequences on shared lettersControlled non-uniform random generation of decomposable structuresIncremental delay enumeration: space and timeCounting, Generating, Analyzing and Sampling Tree AlignmentsUniform random sampling of planar graphs in linear timeUnnamed ItemEnumeration and random generation of accessible automataRandom-Bit Optimal Uniform Sampling for Rooted Planar Trees with Given Sequence of Degrees and ApplicationsRandom Generation of Deterministic Acyclic Automata Using Markov ChainsCounting and generating permutations in regular classesRandom unlabelled graphs containing few disjoint cyclesRandom k -noncrossing RNA structuresExhaustive generation of some lattice paths and their prefixesUnnamed ItemStacks in canonical RNA pseudoknot structuresOn the dependence of the component counting process of a uniform random variableGraph limits of random graphs from a subset of connected k‐treesBoltzmann sampling of ordered structuresUnlabelled Gibbs partitionsThe relevant prefixes of coloured Motzkin walks: an average case analysisVertices of degree k in random unlabeled treesStatistical properties of lambda termsRandom sampling of contingency tables via probabilistic divide-and-conquerVertices of Degree k in Random Unlabeled TreesUnnamed ItemOn 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