Random generation of combinatorial structures from a uniform distribution
From MaRDI portal
Publication:1079379
DOI10.1016/0304-3975(86)90174-XzbMath0597.68056WikidataQ55967168 ScholiaQ55967168MaRDI QIDQ1079379
Vijay V. Vazirani, Mark R. Jerrum, Leslie G. Valiant
Publication date: 1986
Published in: Theoretical Computer Science (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
65C10: Random number generation in numerical analysis
68R99: Discrete mathematics in relation to computer science
Related Items
Approximating the permanent: A simple approach, A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem, A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs, Deterministic and randomized polynomial‐time approximation of radii, Unnamed Item, Unnamed Item, Unnamed Item, Generation of solved instances of Multiconstraint Knapsack problem and its applications to Private Key Cipher, A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph, ANALYSIS OF QUANTUM FUNCTIONS, Counting by quantum eigenvalue estimation, On the computational power of DNA, A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant, On the random generation and counting of matchings in dense graphs, The complexity of controlled selection, On sets polynomially enumerable by iteration, Approximating the permanent of graphs with large factors, Computational complexity of loss networks, The complexity of computing maximal word functions, Monte Carlo approximation of form factors with error bounded a priori, A quasi-polynomial-time algorithm for sampling words from a context-free language, On the number of occurrences of a symbol in words of regular languages., An inequality for polymatroid functions and its applications., Sensitivity analysis of a railway station track layout with respect to a given timetable, An analysis of Monte Carlo algorithm for estimating the permanent, Uniform generation of NP-witnesses using an NP-oracle, Perfect sampling using bounding chains., On approximating weighted sums with exponentially many terms, Counting consistent phylogenetic trees is \#P-complete, Counting and sampling \(H\)-colourings, Note on the knapsack Markov chain., A mildly exponential approximation algorithm for the permanent, On the number of Eulerian orientations of a graph, On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions, The Potts model and the Tutte polynomial, Self-testing algorithms for self-avoiding walks, On the effective generation of set elements within specified ranges, Random Generation for Finitely Ambiguous Context-free Languages
