Bibliographie
- A. Bertoni,
M. Goldwurm, and M. Santini.
Random generation and approximate counting of ambiguously described
combinatorial structure.
In Proceedings of STACS'00, 2000.
- Erkki
Mäkinen and Jarmo Siltaneva.
A note on remy's
algorithm for generating random binary trees.
Technical Report A-2000-2, Department of Computer and Information Sciences,
University of Tampere, 2000.
- Lisa McShine.
Random sampling of
labeled tournaments.
Electronic Journal of Combinatorics, 7(1), 2000.
R8.
- Guy Melancon,
I. Dutour, and M. Bousquet-Melou.
Random generation
of dags for graph drawing.
Technical Report INS-R0005, CWI - Centrum voor Wiskunde en Informatica, March
2000.
- M. Santini.
Random generation and approximate counting of combinatorial structures.
PhD thesis, Università degli Studi di Milano, January 2000.
- C. Banderier,
M. Bousquet-Mélou, A. Denise, Ph. Flajolet, D. Gardy, and
D. Gouyou-Beauchamps.
On generating functions of generating trees.
In Proceedings of 11th Conference on Formal Power Series and Algebraic
Combinatorics (FPSAC'99), pages 40-52, June 1999.
Preliminary version available in INRIA Research Report RR-3661.
(PostScript)
- Elena Barcucci,
Alberto Del Lungo, and Elisa Pergola.
Random generation of trees and other combinatorial objects.
Theoretical Computer Science, 218(2):219-232, 1999.
- A. Bertoni,
M. Goldwurm, and M. Santini.
Random generation and approximate counting of ambiguously described
combinatorial structures.
Technical Report 236-99, Università degli Studi di Milano, Dipartimento di
Scienze dell'Informazione, September 1999.
- A. Denise and
P. Zimmermann.
Uniform random generation of decomposable structures using floating-point
arithmetic.
Theoretical Computer Science, 218:233-248, 1999.
Preliminary version available in INRIA Research Report RR-3242, September 1997.
(PostScript)
- Guy Louchard.
Asymptotic properties of some underdiagonal walks generation algorithms.
Theoretical Computer Science, 218(2):249-262, 1999.
- Mohamed Mosbah and
Nasser Saheb.
Non-uniform random spanning trees on weighted graphs.
Theoretical Computer Science, 218(2):263-271, 1999.
- Gilles Schaeffer.
Random sampling of large planar maps and convex polyhedra.
In Proceedings of STOC'99, Atlanta, 1999.
- Russ Bubley and
Martin Dyer.
Faster random generation of linear extensions.
In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete
Algorithms, pages 350-354, San Francisco, California, 25-27 January
1998.
- Alain Denise, Isabelle
Dutour, and Paul Zimmermann.
CS: a MuPAD package for counting and randomly generating combinatorial
structures.
In Proceedings of 10th Conference on Formal Power Series and Algebraic
Combinatorics (FPSAC'98), pages 195-204, 1998.
Also published in MathPAD 8 (1) 1998.
- J. Diaz, M. Serna, and
P. Spirakis.
On the random generation and counting of matchings in dense graphs.
Theoretical Computer Science, 201(1-2):281-290, 6 July 1998.
Note.
- Philippe Duchon.
On the enumeration and generation of generalized Dyck words.
In Proceedings of 10th Conference on Formal Power Series and Algebraic
Combinatorics (FPSAC'98), pages 221-232, 1998.
- Isabelle Dutour and
Jean-Marc Fédou.
Object grammars and random generation.
Discrete Mathematics and Theoretical Computer Science, 2:47-61,
1998.
- Fripertinger.
Enumeration, construction and random generation of block codes.
IJDCC: Designs, Codes and Cryptography, 14, 1998.
- Diane Hernek.
Random generation of 2 x n contingency tables.
Random Structures and Algorithms, 13(1):71-79, August 1998.
- Christian
Krattenthaler.
Another involution principle-free bijective proof of Stanley's hook-content
formula.
Preprint, 1998.
- Marcus Peinado and
Thomas Lengauer.
Random generation of embedded graphs and an extension to Dobrushin
uniqueness.
In Proceedings of the 30th Annual ACM Symposium on Theory of Computing
(STOC-98), pages 176-185, New York, May 23-26 1998. ACM Press.
- James Gary Propp and
David Bruce Wilson.
How to get a perfectly random sample from a generic Markov chain and generate
a random spanning tree of a directed graph.
Journal of Algorithms, 27(2):170-217, May 1998.
- Gilles Schaeffer.
Conjugaison d'arbres et cartes combinatoires aléatoires.
PhD thesis, Université Bordeaux I, 1998.
- Laurent Alonso, Jean-Luc
Rémy, and René Schott.
A linear-time algorithm for the generation of trees.
Algorithmica, 17:162-182, 1997.
- Laurent Alonso, Jean-Luc Rémy, and
René Schott.
Uniform generaion generation of a schröder tree.
Information Processing Letters, 64(6):305-308, December 1997.
- Russ Bubley and
Martin Dyer.
Faster random
generation of linear extensions.
Technical Report 97.41, School of Computer Studies, University of Leeds, August
1997.
- Alain Denise, Christoph
Dürr, and Fouad Ibn-Majdoub-Hassani.
Enumération et génération aléatoire de polyominos convexes en
réseau hexagonal (French) [enumeration and random generation of convex
polyominoes in the honeycomb lattice].
In Proceedings of 9th Conference on Formal Power Series and Algebraic
Combinatorics (FPSAC'97), pages 222-234, 1997.
- Guy Louchard.
Probabilistic analysis of column convex and directed diagonally convex animals.
Random Structures and Algorithms, 11:151-178, 1997.
- J. G. Propp.
Generating random
elements of a finite distributive lattice.
Electronic Journal of Combinatorics, 4(2), 1997.
R15.
- Gilles Schaeffer.
Bijective census
and random generation of Eulerian planar maps with prescribed vertex
degrees.
Electronic Journal of Combinatorics, 4(1), 1997.
R20.
- Proceedings of the Twenty-Eighth
Annual ACM Symposium on the Theory of Computing, Philadelphia,
Pennsylvania, 22-24 May 1996.
- Laurent Alonso and
René Schott.
A parallel algorithm for the generation of a permutation and applications.
Theoretical Computer Science, 159(1):15-28, 28 May 1996.
- Elena Barcucci,
Alberto Del Lungo, and Renzo Pinzani.
``Deco'' polyominoes, permutations and random generation.
Theoretical Computer Science, 159(1):29-42, 28 May 1996.
- Russ Bubley,
Martin Dyer, and Mark Jerrum.
A new approach
to polynomial-time generation of random points in convex bodies.
Technical report, Department of Computer Science, University of Edinburgh,
April 1996.
Report ECS-LFCS-96-343.
- Alain Denise.
Génération aléatoire et uniforme de mots de langages rationnels
(French) [uniform random generation of words of regular languages].
Theoretical Computer Science, 159(1):43-63, 1996.
- Alain Denise.
Génération aléatoire et uniforme de mots (French) [uniform random
generation of words].
Discrete Mathematics, 153:69-84, 1996.
- Alain Denise, Marcio
Vasconcellos, and Dominic J.A. Welsh.
The random planar graph.
Congressus Numerantium, 113:61-79, 1996.
- Isabelle Dutour.
Grammaires d'objets : énumération, bijections et
génération aléatoire (French) [Object grammars: enumeration,
bijections and random generation].
PhD thesis, Université Bordeaux I, 1996.
- Alan Frieze, Mark
Jerrum, Michael Molloy, Robert Robinson, and Nicholas Wormald.
Generating and counting Hamilton cycles in random regular graphs.
Journal of Algorithms, 21(1):176-198, July 1996.
- Dominique Gouyou-Beauchamps and Jean-Guy Penaud.
Preface: GASCOM '94.
Theoretical Computer Science, 159(1):3-4, 28 May 1996.
- Dominique Gouyou-Beauchamps, Jean-Guy Penaud, and Philippe
Aigrain.
Foreword/Avertissement.
Theoretical Computer Science, 159(1):1-2, 28 May 1996.
Selected Papers from the ``GASCOM '94'' and the ``Polynominoes and Tilings''
workshops.
- W. Hochstättler, M. Loebl, and Christoph Moll.
Generating convex polyominoes at random.
Discrete Mathematics, 153:165-176, 1996.
- Guy Louchard.
Probabilistic analysis of some (un)directed animals.
Theoretical Computer Science, 159(1):65-79, 28 May 1996.
- Mohamed Mosbah.
Probabilistic hyperedge replacement grammars.
Theoretical Computer Science, 159(1):81-102, 28 May 1996.
- Herbert S. Wilf.
Récents développements et problèmes dans le domaine de la génération
aléatoire (French) [recent developments and problems in the area of
random generation].
Theoretical Computer Science, 159(1):5-13, 28 May 1996.
- David Bruce Wilson.
Generating random spanning trees more quickly than the cover time.
In [ACM, 1996], pages 296-303.
- Proceedings of the Sixth
Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco,
California, 22-24 January 1995.
- Laurent Alonso
and René Schott.
Random generation of trees.
Kluwer academic publishers, 1995.
- Frank
Celler, Charles R. Leedham-Green, Scott H. Murray, Alice C. Niemeyer, and
E. A. O'Brien.
Generating random elements of a finite group.
Comm. Algebra, 23:4931-4948, 1995.
- César A. Galindo-Legaria, Arjan Pellenkoft, and Martin L.
Kersten.
Uniformly-distributed random generation of join orders.
In [Gottlob and Vardi, 1995], pages
280-293.
- Massimiliano Goldwurm.
Random generation of words in an algebraic language in linear binary space.
Information Processing Letters, 54:229-233, 1995.
- V. Gore and Mark Jerrum.
A quasi-polynomial-time algorithm for sampling words from a context-free
language.
Technical Report ECS-LFCS-95-326, LFCS, July 1995.
- Georg Gottlob and
Moshe Y. Vardi, editors.
Database Theory--ICDT'95, 5th International Conference, volume
893 of Lecture Notes in Computer Science, Prague, Czech
Republic, 11-13 January 1995. Springer.
- S. Kannan, Z Sweedyk, and
S Mahaney.
Counting and random generation of strings in regular languages.
In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete
Algorithms, pages 551-557, San Francisco, California, January
1995.
- Vincent Vajnovski.
Listing and random generation of neuronal trees coded by six letters.
ACAM, 4(1):29-40, 1995.
- Laurent Alonso.
Uniform generation of a Motzkin word.
Theoretical Computer Science, 134:529-536, 1994.
- M. D. Atkinson and J. R.
Sack.
Uniform generation of forests of restricted height.
Information Processing Letters, 50(6):323-327, June 1994.
- Elena Barcucci, Renzo
Pinzani, and Renzo Sprugnoli.
The random generation of directed animals.
Theoretical Computer Science, 127(2):333-350, 1994.
- Alain Denise.
Enumération et génération aléatoire de chemins (French) [enumeration
and random generation of paths].
In Proceedings of 6th Conference on Formal Power Series and Algebraic
Combinatorics (FPSAC'94), pages 91-97. DIMACS, Rutgers University,
1994.
- Alain Denise.
Méthodes de génération aléatoire d'objets combinatoires de grande
taille et problèmes d'énumération.
PhD thesis, Université Bordeaux I, 1994.
- Philippe Flajolet,
Paul Zimmermann, and Bernard Van Cutsem.
A calculus for the random generation of labelled combinatorial structures.
Theoretical Computer Science, 132:1-35, 1994.
A preliminary version is available in INRIA Research Report RR-1830.
- H. G. Mairson.
Generating words in a context free language uniformly at random.
Information Processing Letters, 49:95-99, 1994.
- Paul Zimmermann.
Gaïa: a package for the random generation of combinatorial structures.
MapleTech, 1(1):38-46, 1994.
- Jean Berstel and
Michel Pocchiola.
Random generation of finite Sturmian words.
In Proceedings of 5th Conference on Formal Power Series and Algebraic
Combinatorics (FPSAC'93), pages 69-82. Université de Florence,
1993.
- David Feldman,
Russell Impagliazzo, Moni Naor, Noam Nisan, Steven Rudich, and Adi Shamir.
On dice and coins: Models of computation for random generation.
Information and Computation, 104(2):159-174, June 1993.
- Philippe Flajolet, Paul
Zimmermann, and Bernard Van Cutsem.
A calculus for the random
generation of labelled combinatorial structures.
Technical Report RR-1830, INRIA, January 1993.
- Laurent Alonso.
Structures arborescentes : algorithmes de génération, problème de
l'inclusion, relations maximin.
PhD thesis, Université Paris XI Orsay, 1992.
- M. D. Atkinson and J. R.
Sack.
Generating binary trees at random.
Information Processing Letters, 41:21-23, 1992.
- Elena Barcucci, Renzo
Pinzani, and Renzo Sprugnoli.
The random generation of underdiagonal walks.
In Pierre Leroux and Christophe Reutenauer, editors, Proceedings of 4th
Conference on Formal Power Series and Algebraic Combinatorics
(FPSAC'92). Université du Québec à Montréal, 1992.
- P. Epstein and
J.-R. Sack.
Generating triangulations at random.
In Proc. 4th Canad. Conf. Comput. Geom., pages 305-310, 1992.
- Alistair Sinclair.
Algorithms for Random Generation and Counting, a Markov Chain
Approach.
Birkhaüser, 1992.
- Proceedings of the Twenty Third
Annual ACM Symposium on Theory of Computing, New Orleans, Louisiana,
6-8 May 1991.
- László Babai.
Local expansion of vertex-transitive graphs and random generation in finite
groups.
In [ACM, 1991], pages 164-174.
- M. E. Agishtein and
A. A. Migdal.
Recursive sampling of planar graphs and fractal properties of a two-dimensional
quantum gravity.
Internat. J. Modern Phys. C, 1(1):165-179, 1990.
- David J. Aldous.
A random walk construction of uniform spanning trees and uniform labelled
trees.
SIAM Journal on Discrete Mathematics, 3(4):450-465, 1990.
- Mark Jerrum and
Alistair Sinclair.
Fast uniform generation of regular graphs.
Theoretical Computer Science, 73:91-100, 1990.
- V. G. Kulkarni.
Generating random combinatorial objects.
Journal of Algorithms, 11(2):185-207, June 1990.
- B. D. McKay and N. C.
Wormald.
Uniform generation of random regular graphs of moderate degree.
Journal of Algorithms, 11:52-67, 1990.
- G. Tinhofer.
Generating graphs uniformly at random.
Computing Supplementum, 7:235-255, 1990.
- Giorgio Ausiello,
Mariangiola Dezani-Ciancaglini, and Simona Ronchi Della Rocca, editors.
Automata, Languages and Programming, 16th International
Colloquium, volume 372 of Lecture Notes in Computer
Science, Stresa, Italy, 11-15 July 1989. Springer-Verlag.
- Andrei Broder.
Generating random spanning trees.
In 30th Annual Symposium on Foundations of Computer
Science [IEE, 1989], pages 442-447.
- David Feldman,
Russell Impagliazzo, Moni Naor, Noam Nisan, Steven Rudich, and Adi Shamir.
On dice and coins: Models of computation for random generation.
In [Ausiello et al., 1989], pages
319-340.
- IEEE.
30th Annual Symposium on Foundations of Computer Science, Research
Triangle Park, North Carolina, 30 October-1 November 1989.
- Mark Jerrum and
Alistair Sinclair.
Approximating the permanent.
SIAM Journal on Computing, 18(6):1149-1178, December 1989.
- H. W. Martin and B. J. Orr.
A random binary tree generator.
In Computing Trends in the 1990's, ACM Seventeenth Computer Science
Conference, pages 33-38, Louisville, Kentucky, 1989. ACM Press.
- Quiroz.
Fast random generation of binary, t-ary and other types of trees.
CLASSIF: Journal of Classification, 6, 1989.
- Alistair Sinclair and
M. R. Jerrum.
Approximate counting, uniform generation and rapidly mixing Markov chains.
Information and Computation, 82:93-133, 1989.
- Herbert S. Wilf.
Combinatorial Algorithms : An Update.
SIAM, 1989.
- David Gries and Jin Yun Xue.
Generating a random cyclic permutation.
BIT, 28(3):569-572, 1988.
- J.M. Pallo.
Generating trees with n nodes and m leaves.
Int. J. Comp. Math, 21:133-144, 1987.
- N. C. Wormald.
Generating random unlabelled graphs.
SIAM J. Comput, 16(4):717-727, 1987.
- Luc Devroye.
Non-uniform random variate generation.
Springer Verlag, 1986.
- Mark R. Jerrum, L. G.
Valiant, and V. V. Vazirani.
Random generation of combinatorial structures from a uniform distribution.
Theoretical Computer Science, 43:169-188, 1986.
- S. F. Altschul and
B. W. Erickson.
Significance of nucleotide sequence alignments: a method for random sequence
permutation that preserves dinucleotide and codon usage.
Mol. Biol. Evol., 2(6):526-538, 1985.
- Mark R. Jerrum.
Random generation of combinatorial structures from a uniform distribution.
Lecture Notes in Computer Science, 194:290-299, 1985.
Proceedings of the 12th Colloquium Automata, Languages and Programming.
- Jean-Luc Rémy.
Un procédé itératif de dénombrement d'arbres binaires et son
application à leur génération aléatoire (French) [an iterative
method for counting binary trees, and application to their random
generation].
R. AI. R. O Informatique Théorique, 19(2):179-195, 1985.
- N. C. Wormald.
Generating random regular graphs.
J. Algorithms, 5:247-280, 1984.
- J. D. Dixon and Herbert S.
Wilf.
The random selection of unlabeled graphs.
J. Algorithms, 4:205-213, 1983.
- Alain Guénoche.
Random spanning tree.
Journal of Algorithms, 4(3):214-220, September 1983.
- Timothy Hickey and
J. Cohen.
Uniform random generation of strings in a context-free language.
SIAM. J. Comput, 12(4):645-655, 1983.
- Persi Diaconis and
Mehrdad Shahshahani.
Generating a random permutation with random transpositions.
Zeitschrift für Wahrscheinlichkeitstheorie und verwandte
Gebiete, 57:159-179, 1981.
- Herbert S. Wilf.
The uniform selection of free trees.
Journal of Algorithms, 2:204-207, 1981.
- D.B. Arnold and M.R.
Sleep.
Uniform random generation of balanced parenthesis strings.
ACM Trans. Programming Languages and Systems, 2(1):122-128,
1980.
- A. Proskurowski.
On the generation of binary trees.
J. A.C.M, 27(1):1-2, 1980.
- A. Nijenhuis and
Herbert S. Wilf.
Combinatorial algorithms.
Academic Press Inc., 1979.
- G. Tinhofer.
On the generation of random graphs with given properties and known
distribution.
Appl. Comput. Sci. Ber. Prakt. Inf., 13:265-296, 1979.
- Herbert S. Wilf.
A unified setting for sequencing, ranking, and selection algorithms for
combinatorial objects.
Advances in Mathematics, 24:281-291, 1977.