%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%									%
%                            GASCom group                               %
%                                                                       %
%	Publications concernant la generation aleatoire	de structures   %
%       combinatoires.                                                  %
%                                                                       %
%       References on random generation of combinatorial structures.    %
%                                                                       %
%       http://www.lri.fr/~denise/GASCOM/gascompubli.bib                %
%                                                                       %
%	Last update: August 25, 2000                                    %
%									%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

@string{tcs = {Theoretical Computer Science}}
@string{lncs={Lecture Notes in Computer Science}}
@string{iandcomp={Information and Computation}}
@string{rsa={Random Structures and Algorithms}}
@string{jalgo = "Journal of Algorithms"}
@string{sicomp = "SIAM Journal on Computing"}

@Article{AgMi90,
  author = 	 {Agishtein, M. E. and Migdal, A. A.},
  title = 	 {Recursive sampling of planar graphs and fractal properties 
                  of a two-dimensional quantum gravity},
  journal = 	 {Internat. J. Modern Phys. C},
  year = 	 1990,
  volume =	 1,
  number =	 1,
  pages =	 {165--179}
}

@Article{AlEr85,
  author =       "S. F. Altschul and B. W. Erickson",
  title =        "Significance of nucleotide sequence alignments: a
                 method for random sequence permutation that preserves
                 dinucleotide and codon usage.",
  journal =      "Mol. Biol. Evol.",
  volume =       "2",
  number =       "6",
  pages =        "526--538",
  year =         "1985",
}

@Article{AlReSc97,
  author = 	 {Alonso, Laurent and Rémy, Jean-Luc and Schott, Ren\'e},
  title = 	 {A linear-time algorithm for the generation of trees},
  journal = 	 {Algorithmica},
  year = 	 {1997},
  volume = 	 {17},
  pages = 	 {162--182}
}

@Article{Aldous90,
  author = 	 {David J. Aldous},
  title = 	 {A random walk construction of uniform spanning trees and uniform labelled trees},
  journal = 	 {SIAM Journal on Discrete Mathematics},
  year = 	 1990,
  volume =	 3,
  number =	 4,
  pages =	 {450--465}
}

@PhdThesis{Alo92,
	author	= "Laurent Alonso",
	title	= "Structures arborescentes : algorithmes de g\'en\'eration,
			probl\`eme de l'inclusion, relations maximin",
	school	= "Universit\'e Paris XI Orsay",
	year	= "1992",
}

@Article{Alonso95,
  author = 	 {Alonso, Laurent},
  title = 	 {Uniform generation of a {M}otzkin word},
  journal = 	 {Theoretical Computer Science},
  year = 	 {1994},
  volume = 	 {134},
  pages = 	 {529--536}
}

@Book{Alonso95:_random,
  author =	 {Laurent Alonso and Ren{\'e} Schott},
  title = 	 {Random generation of trees},
  publisher = 	 {Kluwer academic publishers},
  year = 	 1995
}

@Article{AlonsoS1996,
title={A parallel algorithm for the generation of a permutation and
applications},
author={Laurent Alonso and Ren{\'e} Schott},
pages={15--28},
journal=tcs,
month={28~} # may,
year=1996,
volume=159,
number=1,
}

@article{ArSl80,
	author	= "D.B. Arnold and M.R. Sleep", 
        title	= "Uniform random generation of balanced parenthesis strings", 
        journal	= "ACM Trans. Programming Languages and Systems",
        volume	= "2",
        number  = {1},
        year	= "1980",
        pages	= "122-128"
}

@article{AtSa92,
	author	= "M. D. Atkinson and J. R. Sack", 
        title	= "Generating binary trees at random", 
        journal	= "Information Processing Letters",
        volume	= "41",
        year	= "1992",
        pages	= "21-23"
}

@Article{AtSa94,
  author =       "M. D. Atkinson and J. -R. Sack",
  title =        "Uniform generation of forests of restricted height",
  journal =      "Information Processing Letters",
  volume =       "50",
  number =       "6",
  pages =        "323--327",
  month =        jun,
  year =         "1994",
}

@inproceedings{BBDFGG99E,
title = "On generating functions of generating trees",
author = "C.~Banderier and M.~Bousquet-Mélou and A.~Denise and Ph.~Flajolet and D.~Gardy and D.~Gouyou-Beauchamps",
year = "1999",
month = {June},
booktitle = "Proceedings of 11th Conference on Formal Power
                     Series and Algebraic Combinatorics (FPSAC'99)", 
pages = "40--52",
organisation = "Barcelone",
note = "Preliminary version available in INRIA Research Report RR-3661",
postscript = "http://www.inria.fr/RRRT/RR-3661.html",
type_publi = "icolcomlec"
}

@inproceedings{BaPiSp92,
	author	= "Elena Barcucci and  Renzo Pinzani and Renzo Sprugnoli", 
	title	= "The random generation of underdiagonal walks",
	booktitle = "Proceedings of 4th Conference on Formal Power
                     Series and Algebraic Combinatorics (FPSAC'92)", 
        year	= "1992",
        editor	= "Pierre Leroux and Christophe Reutenauer",
        publisher = "Universit\'e du Qu\'ebec \`a Montr\'eal"
}

@Article{BaPiSp94,
  author = 	 {Elena Barcucci and  Renzo Pinzani and Renzo Sprugnoli},
  title = 	 {The random generation of directed animals},
  journal = 	 {Theoretical Computer Science},
  year = 	 {1994},
  volume = 	 {127},
  number = 	 {2},
  pages = 	 {333-350},
}


@InProceedings{Babai91,
title={Local Expansion of Vertex-Transitive Graphs and Random Generation
in Finite Groups},
author={Babai, L{\'a}szl{\'o}},
pages={164--174},
crossref={STOC23},
}

@Article{Barcucci99:_random,
  author = 	 {Elena Barcucci and Alberto Del Lungo and Elisa Pergola},
  title = 	 {Random generation of trees and other combinatorial objects},
  journal = 	 tcs,
  year = 	 1999,
  volume =	 218,
  number =	 2,
  pages =	 {219--232}
}

@Article{BarcucciLP1996,
title={{``Deco''} polyominoes, permutations and random generation},
author={Elena Barcucci and Alberto Del Lungo and Renzo Pinzani},
pages={29--42},
journal=tcs,
month={28~} # may,
year=1996,
volume=159,
number=1,
}


@Article{,
  author = 	 {Alonso, Laurent and Rémy, Jean-Luc and Schott, Ren\'e},
  title = 	 {Uniform generaion generation of a Schr\"oder tree},
  journal = 	 {Information Processing Letters},
  year = 	 1997,
  volume =	 64,
  number =	 6,
  pages =	 {305--308},
  month =	 {December}
}


@inproceedings{BePo93,
	author = {Jean Berstel and Michel Pocchiola},
	title = "Random Generation of Finite {Sturmian} Words",
	booktitle = "Proceedings of 5th Conference on Formal Power
                     Series and Algebraic Combinatorics (FPSAC'93)", 
        organization = "Universit\'e de Florence",
        year	= "1993",
        pages = {69-82}
}



@InProceedings{Bertoni00:_random,
  author =	 {Bertoni, A. and Goldwurm, M. and Santini, M.},
  title =	 {Random generation and approximate counting of
                  ambiguously described combinatorial structure},
  booktitle =	 {Proceedings of STACS'00},
  year =	 2000
}

@TechReport{Bertoni99:_random,
  author = 	 {Bertoni, A. and Goldwurm, M. and Santini, M.},
  title = 	 {Random generation and approximate counting 
                  of ambiguously described combinatorial structures},
  institution =  {Universit\`a degli Studi di Milano, 
                  Dipartimento di Scienze dell'Informazione},
  year = 	 1999,
  number =	 {236-99},
  month =	 {September},
  url = { http://zorn.usr.dsi.unimi.it/~santini/FTP/papers/ridsi-236-99.ps.gz}
}

@PhdThesis{SantiniPhD,
  author =	 {Santini, M.},
  title =	 {Random generation and approximate counting of
                  combinatorial structures},
  school =	 {Universit\`a degli Studi di Milano},
  year =	 2000,
  month =	 {January},
  url = {http://zorn.usr.dsi.unimi.it/~santini/FTP/papers/phd.ps.gz}
}

@InProceedings{Broder89,
title={Generating Random Spanning Trees},
author={Broder, Andrei},
pages={442--447},
crossref={FOCS30},
}

@techreport{BubleyDyer97d, 
author = 
     {Russ Bubley and Martin Dyer}, 
title = 
     {Faster Random Generation of Linear Extensions}, 
institution = 
     {School of Computer Studies, University of Leeds}, 
number = 
     {97.41}, 
month = 
     aug, 
year = 
     1997, 
abstract = 
     {
     This paper examines the problem of sampling (almost) uniformly from the set of linear
     extensions of a partial order, a classic problem in the theory of approximate sampling.
     Previous techniques have relied on deep geometric arguments, or have not worked in full
     generality. Recently, focus has centred on the Karzanov and Khachiyan Markov chain. In
     this paper, we define a slightly different Markov chain, and present a very simple proof of
     its rapid mixing, using the method of path coupling. We show that this chain has mixing time
     $O(n^3 \log n)$, which significantly improves the previous best bound for this problem,
     which was a bound of $O(n^5 \log n)$, for the Karzanov and Khachiyan chain.

     We also show how a classical metric, Spearman's footrule, may be reformulated in terms
     of transpositions.
     }, 
url = {http://www.scs.leeds.ac.uk/russ/papers/obtaining.html}
}

@inproceedings{BubleyDyer97e, 
author = 
     {Russ Bubley and Martin Dyer}, 
title = 
     {Faster Random Generation of Linear Extensions}, 
booktitle = 
     {Proceedings of the Ninth Annual {ACM}-{SIAM} Symposium on Discrete
     Algorithms}, 
month = 
     {25--27 } # jan, 
year = 
     1998, 
address = 
     {San Francisco, California}, 
pages = 
     {350--354}, 
abstract = 
     {
     This paper examines the problem of sampling (almost) uniformly from the set of linear
     extensions of a partial order, a classic problem in the theory of approximate sampling.
     Previous techniques have relied on deep geometric arguments, or have not worked in full
     generality. Recently, focus has centred on the Karzanov and Khachiyan Markov chain. In
     this paper, we define a slightly different Markov chain, and present a very simple proof of
     its rapid mixing, using the method of path coupling. We show that this chain has mixing time
     $O(n^3 \log n)$, which significantly improves the previous best bound for this problem,
     which was a bound of $O(n^5 \log n)$, for the Karzanov and Khachiyan chain.

     We also show how a classical metric, Spearman's footrule, may be reformulated in terms
     of transpositions.
     } 
}

@techreport{BubleyDyerJerrum96, 
author = {Russ Bubley and Martin Dyer and Mark Jerrum}, 
title = {A New Approach to Polynomial-Time Generation of Random Points in Convex Bodies}, 
institution = {Department of Computer Science, University of Edinburgh}, 
month =  apr, 
note = {Report ECS-LFCS-96-343}, 
year = 1996, 
abstract = { In this paper we describe a new method for proving the 
         polynomial-time convergence of
         an algorithm for sampling (almost) uniformly at random from 
         a convex-body in high
         dimension. Previous approaches have been based 
         on estimating conductance via
         isoperimetric inequalities. We show that a conceptually 
         simpler coupling argument can be
         used to give a similar result.},
url = {http://www.scs.leeds.ac.uk/russ/papers/obtaining.html}
}

@Article{CellerLeedhamGreenetal95,
  author =       "Frank Celler and Charles R.\ Leedham-Green and Scott
                 H.\ Murray and Alice C.\ Niemeyer and E. A.\ O'Brien",
  title =        "Generating random elements of a finite group",
  journal =      "Comm.\ Algebra",
  volume =       "23",
  pages =        "4931--4948",
  year =         "1995",
}

@Article{DZ99R,
title   = "Uniform Random Generation of Decomposable Structures
           Using Floating-Point Arithmetic",
author  = "A. Denise and P. Zimmermann",
year    = "1999",
journal = tcs,
volume  = 218,
pages   = "233--248",
note    = "Preliminary version available in INRIA Research Report RR-3242, September 1997",
postscript = "http://www.inria.fr/RRRT/RR-3242.html",
type-publi = "irevcomlec"
}

@PhdThesis{Den94,
	author	= "Alain Denise",
	title	= "M\'ethodes de g\'en\'eration al\'eatoire d'objets
		  combinatoires de grande taille et probl\`emes d'\'enum\'eration",
	school	= "Universit\'e Bordeaux I",
	year	= "1994"
}

@inproceedings{Den94E,
author = {Alain Denise},
title = "Enum\'eration et g\'en\'eration al\'eatoire de chemins
         ({F}rench) [Enumeration and random generation of paths]",
booktitle = "Proceedings of 6th Conference on Formal Power
                     Series and Algebraic Combinatorics (FPSAC'94)", 
organization = "DIMACS, Rutgers University",
year	= "1994",
pages = {91-97}
}

@article{Den96a,
		  author="Denise, Alain",
		  title="G\'en\'eration al\'eatoire et uniforme de
		  mots ({F}rench) [Uniform random generation of words]",
		  journal="Discrete Mathematics",
		  volume="153",
		  year="1996",
		  pages="69-84"
		  }

@article{Den96b,
		  author="Denise, Alain",
		  title="G\'en\'eration al\'eatoire et uniforme de
		  mots de langages rationnels ({F}rench) [Uniform random generation
                  of words of regular languages]",
		  journal="Theoretical Computer Science",
		  volume="159",
		  number=1,
		  year="1996",
		  pages="43-63"
		  }

@article{Den96c,
		  author="Denise, Alain and Vasconcellos, Marcio and Welsh, Dominic J.A.",
		  title="The random planar graph",
		  journal="Congressus Numerantium",
		  volume="113",
		  year="1996",
		  pages="61-79"
		  }

@book{Dev86,
	author	= "Luc Devroye",
	title	= "Non-uniform random variate generation",
	publisher="Springer Verlag",
	year	= "1986"
}

@Article{DiSh81,
  author =       "Persi Diaconis and Mehrdad Shahshahani",
  title =        "Generating a random permutation with random
                 transpositions",
  journal =      "Zeitschrift f{\"u}r Wahrscheinlichkeitstheorie und
                 verwandte Gebiete",
  year =         "1981",
  volume =       "57",
  pages =        "159--179",
  owner =        "bs",
}


@article{DiWi83,
	author=	"J. D. Dixon and  Herbert S. Wilf",
	title=	"The random selection of unlabeled graphs",
	journal= "J. Algorithms",
	volume=	"4",
	year=	"1983",
	pages=	"205-213"
}


@Article{DiazSS1998,
title={On the random generation and counting of matchings in dense
graphs},
author={J. Diaz and M. Serna and P. Spirakis},
pages={281--290},
journal=tcs,
month={6~} # jul,
year=1998,
volume=201,
number={1--2},
note={Note},
}

@Conference{DDIMH97E,
title = "Enum{\'e}ration et g{\'e}n{\'e}ration al{\'e}atoire 
         de polyominos convexes en r{\'e}seau hexagonal
         ({F}rench) [Enumeration and random generation of convex polyominoes
         in the honeycomb lattice]",
author = "Denise, Alain and D{\"u}rr, Christoph and Ibn-Majdoub-Hassani, Fouad",
year = "1997",
pages = "222-234",
booktitle = "Proceedings of 9th Conference on Formal Power
                     Series and Algebraic Combinatorics (FPSAC'97)", 
organisation = "Vienna"
}

@Conference{DDZ98E,
title = "{CS}: a {MuPAD} package for counting and randomly generating 
         combinatorial structures",
author = "Denise, Alain and Dutour, Isabelle and Zimmermann, Paul",
year = "1998",
booktitle = "Proceedings of 10th Conference on Formal Power
                     Series and Algebraic Combinatorics (FPSAC'98)", 
organisation = "Toronto",
pages = "195--204",
note = "Also published in MathPAD 8 (1) 1998",
url = "http://dept-info.labri.u-bordeaux.fr/\~dutour/PAPERS/cs-fpsac.ps.gz",
}

@PhdThesis{Dutour96,
  author = 	 {Isabelle Dutour},
  title = 	 {Grammaires d'objets : \'enum\'eration, bijections 
                  et g\'en\'eration al\'eatoire ({F}rench) [Object grammars: enumeration, 
                  bijections and random generation]},
  school = 	 {Universit\'e Bordeaux I},
  year = 	 {1996},
  url = {http://www.labri.u-bordeaux.fr/Equipe/CombEnum/membre/dutour/PAPERS/these.ps.gz}
}

@article{Dutour98,
	author	= "Isabelle Dutour and Jean-Marc F\'edou",
	title	= "Object grammars and random generation",
	journal	= "Discrete Mathematics and Theoretical Computer Science",
	volume	=  "2",
	year	= "1998",
	pages	= "47--61"
}

@InProceedings{Epstein:1992:GTA,
  author =       "P. Epstein and J.-R. Sack",
  title =        "Generating triangulations at random",
  booktitle =    "Proc. 4th Canad. Conf. Comput. Geom.",
  year =         "1992",
  pages =        "305--310",
}

@Proceedings{FOCS30,
title={30th Annual Symposium on Foundations of Computer Science},
booktitle={30th Annual Symposium on Foundations of Computer Science},
month={30 } # oct # {--1 } # nov,
year=1989,
address={Research Triangle Park, North Carolina},
organization={IEEE},
crossrefonly=1,
}

@InProceedings{FeldmanINNRS1989,
title={On Dice and Coins: Models of Computation for Random Generation},
author={David Feldman and Russell Impagliazzo and Moni Naor and Noam
Nisan and Steven Rudich and Adi Shamir},
crossref={icalp89},
pages={319--340},
}

@Article{FeldmanINNRS93,
title={On Dice and Coins: Models of Computation for Random Generation},
author={David Feldman and Russell Impagliazzo and Moni Naor and Noam
Nisan and Steven Rudich and Adi Shamir},
pages={159--174},
journal=iandcomp,
month=jun,
year=1993,
volume=104,
number=2,
}

@TechReport{FlZiCu93R,
  author = 	 {Philippe Flajolet and Paul Zimmermann and {Van Cutsem}, Bernard},
  title = 	 {A Calculus for the Random Generation of
                   Labelled Combinatorial Structures},
  institution =  {INRIA},
  year = 	 1993,
  number =	 {RR-1830},
  month =	 {January},
  url = "http://www.inria.fr/RRRT/RR-1830.html"
}

@article{FlZiCu94TCS,
	author	= "Philippe Flajolet and Paul Zimmermann and {Van Cutsem}, Bernard",
	title	= "A Calculus for the Random Generation of
                   Labelled Combinatorial Structures",
	journal	= "Theoretical Computer Science",
	volume	=  "132",
	year	= "1994",
	pages	= "1-35",
        note = "A preliminary version is available in 
                INRIA Research Report RR-1830",
}




@Article{FrJeMoRoWo96,
  title =        "Generating and Counting {Hamilton} Cycles in Random
                 Regular Graphs",
  author =       "Alan Frieze and Mark Jerrum and Michael Molloy and
                 Robert Robinson and Nicholas Wormald",
  pages =        "176--198",
  journal =      "Journal of Algorithms",
  year =         "1996",
  month =        jul,
  volume =       "21",
  number =       "1",
}

@Conference{Duchon98,
title = "On the enumeration and generation of generalized {Dyck} words",
author = "Duchon, Philippe",
year = "1998",
booktitle = "Proceedings of 10th Conference on Formal Power
                     Series and Algebraic Combinatorics (FPSAC'98)", 
organisation = "Toronto",
pages = "221--232"
}


@Article{Fripertinger98,
  author =       "Fripertinger",
  title =        "Enumeration, Construction and Random Generation of
                 Block Codes",
  journal =      "IJDCC: Designs, Codes and Cryptography",
  volume =       "14",
  year =         "1998",
}

@InProceedings{Galindo-LegariaPK1995,
title={Uniformly-Distributed Random Generation of Join Orders},
author={C{\'e}sar A. Galindo-Legaria and Arjan Pellenkoft and Martin L.
Kersten},
pages={280--293},
crossref={ICDT95},
}


@Article{Gol95,
  author = 	 "Massimiliano Goldwurm",
  title = 	 "Random generation of words in an algebraic language
		  in linear binary space",
  journal = 	 "Information Processing Letters",
  year = 	 "1995",
  volume = 	 "54",
  pages = 	 "229-233",
}

@TechReport{Gore95,
  author = 	 {V. Gore and Mark Jerrum},
  title = 	 {A quasi-polynomial-time algorithm for sampling words 
                  from a context-free language},
  institution =  {LFCS},
  year = 	 1995,
  number =	 {ECS-LFCS-95-326},
  month =	 {July},
  url = "http://www.dcs.ed.ac.uk/lfcsreps/EXPORT/95/ECS-LFCS-95-326/index.html"
}

@Article{Gouyou-BeauchampsP1996,
title={Preface: {GASCOM '94}},
author={Dominique Gouyou-Beauchamps and Jean-Guy Penaud},
pages={3--4},
journal=tcs,
month={28~} # may,
year=1996,
volume=159,
number=1,
}

@Article{Gouyou-BeauchampsPA1996,
title={{Foreword/Avertissement}},
author={Dominique Gouyou-Beauchamps and Jean-Guy Penaud and Philippe
Aigrain},
pages={1--2},
journal=tcs,
month={28~} # may,
year=1996,
volume=159,
number=1,
note={Selected Papers from the ``GASCOM '94'' and the ``Polynominoes
and Tilings'' workshops},
}

@Article{GrJi88,
  author =       "David Gries and Jin Yun Xue",
  title =        "Generating a random cyclic permutation",
  journal =      "BIT",
  volume =       "28",
  number =       "3",
  pages =        "569--572",
  year =         "1988",
}


@Article{Guenoche83,
title={Random Spanning Tree},
author={Alain Gu{\'e}noche},
pages={214--220},
journal=jalgo,
year=1983,
month=sep,
volume=4,
number=3,
}

@Article{Hernek98,
  author = 	 {Hernek, Diane},
  title = 	 {Random generation of $2 x n$ contingency tables},
  journal = 	 rsa,
  year = 	 1998,
  volume =	 13,
  number =	 1,
  month =        aug,
  pages =	 {71--79}
}

@article{HiCo83,
	author	= "Timothy Hickey and J. Cohen",
	title	= "Uniform Random Generation of Strings 
	           in a Context-Free Language",
	journal	= "SIAM. J. Comput",
	volume	= "12",
        number = {4},
	year	= "1983",
	pages	= "645-655"
}

@Article{HoLoMo96,
  author = 	 {W. Hochst\"{a}ttler and M. Loebl and Christoph Moll},
  title = 	 {Generating Convex Polyominoes at Random},
  journal = 	 {Discrete Mathematics},
  year = 	 {1996},
  volume = 	 {153},
  pages = 	 {165-176},
}

@Proceedings{ICALP89,
editor={Giorgio Ausiello and Mariangiola Dezani-Ciancaglini and Simona
Ronchi Della Rocca},
title={Automata, Languages and Programming, 16th International
Colloquium},
booktitle={Automata, Languages and Programming, 16th International
Colloquium},
address={Stresa, Italy},
month={11--15~} # jul,
year=1989,
series=lncs,
volume=372,
publisher={Springer-Verlag},
comment={ISBN 3-540-51371-X},
crossrefonly=1,
}

@Proceedings{ICDT95,
editor={Georg Gottlob and Moshe Y. Vardi},
title={Database Theory---ICDT'95, 5th International Conference},
booktitle={Database Theory---ICDT'95, 5th International Conference},
address={Prague, Czech Republic},
month={11--13 } # jan,
year=1995,
series=lncs,
volume=893,
publisher={Springer},
comment={ISBN 3-540-58907-4},
crossrefonly=1,
}

@article{JeSi90,
	author=	"Mark Jerrum and Alistair Sinclair",
	title=	"Fast uniform generation of regular graphs",
	journal= "Theoretical Computer Science",
	volume=	"73",
	year=	"1990",
	pages=	"91-100"
}
		  
@article{JeVaVa86,
	author=	"Mark R. Jerrum and L. G. Valiant and V. V. Vazirani",
	title=	"Random generation of combinatorial structures from a
		uniform distribution",
	journal="Theoretical Computer Science",
	volume=	"43",
	year=	"1986",
	pages=	"169-188"
}
		  
@article{Jer85,
	author=	"Mark R. Jerrum",
	title=	"Random generation of combinatorial structures from a
		uniform distribution",
	journal="Lecture Notes in Computer Science",
	volume=	"194",
	year=	"1985",
	pages=	"290-299",
	note=	"Proceedings of the 12th Colloquium Automata, Languages
		and Programming"
}

@Article{JerrumS89,
title={Approximating the Permanent},
author={Mark Jerrum and Alistair Sinclair},
pages={1149--1178},
journal=sicomp,
year=1989,
month=dec,
volume=18,
number=6,
preliminary={STOC::JerrumS1988:235},
}

@InProceedings{KaSwMa95,
  author = 	 {Kannan, S. and Sweedyk, Z and Mahaney, S},
  title = 	 {Counting and random generation of strings in regular languages},
  booktitle = 	 {Proceedings of the Sixth Annual {ACM}-{SIAM} Symposium on
  Discrete Algorithms},
  year = 	 {1995},
  address = 	 {San Francisco, California},
  month = 	 {January},
  pages = 	 {551--557}
}

@Unpublished{Krattenthaler98,
  author = 	 {Christian Krattenthaler},
  title = 	 {Another involution principle-free bijective proof of
                  {S}tanley's hook-content formula},
  note = 	 {Preprint},
  url = {http://radon.mat.univie.ac.at/People/kratt/artikel/stanpak.html},
  year =	 1998
}

@Article{Kulkarni90,
title={Generating Random Combinatorial Objects},
author={V. G. Kulkarni},
pages={185--207},
journal=jalgo,
year=1990,
month=jun,
volume=11,
number=2,
}

@Article{Louchard1996,
title={Probabilistic analysis of some (un)directed animals},
author={Guy Louchard},
pages={65--79},
journal=tcs,
month={28~} # may,
year=1996,
volume=159,
number=1,
}

@Article{Louchard97,
  author = 	 {Guy Louchard},
  title = 	 {Probabilistic analysis of column convex and directed diagonally convex animals},
  journal =rsa,
  year = 	 1997,
  volume =	 11,
  pages =	 {151--178}
}

@Article{Louchard99,
  author = 	 {Guy Louchard},
  title = 	 {Asymptotic properties of some underdiagonal walks generation algorithms},
  year = {1999},
  journal =tcs,
  volume = 218,
  number = 2,
  pages = {249--262}
}

@article{MKWo90,
	author = "B. D. McKay and N. C. Wormald",
	title = "Uniform Generation of Random Regular Graphs of Moderate
		Degree", 
	journal = "Journal of Algorithms",
	volume = 11,
	year = 1990,
	pages = "52-67"
}

@inproceedings{MaOr89,
  author = {H. W. Martin and B. J. Orr},
  title = {A random binary tree generator},
  booktitle = {Computing Trends in the 1990's, ACM Seventeenth
		  Computer Science Conference},
  year = {1989},
  publisher = {ACM Press},
  pages = {33-38},
  address = {Louisville, Kentucky}
}

@TechReport{MaSi2000,
  author =       "Erkki M{\"a}kinen and Jarmo Siltaneva",
  title =        "A note on Remy's algorithm for generating random
                 binary trees",
  institution =  "Department of Computer and Information Sciences,
                 University of Tampere",
  year =         "2000",
  number =       "A-2000-2",
  abstract =     "This note discusses the implementation of R\'{e}my's
                 algorithm for generating unbiased random binary trees.
                 We point out an error in a published implementation of
                 the algorithm. The error is found by using the
                 chi-square test. Moreover, a correct implementation of
                 the algorithm is presented.",
  url =          "ftp://ftp.cs.uta.fi/pub/reports/A-2000-2.ps.Z",
}


@article{Mai94,
     author = 	 "H. G. Mairson",
     title = 	 "Generating Words in a Context Free Language
		     Uniformly at Random",
     journal =	 {Information Processing Letters},
     volume =    49,
     year = 	 1994,
     pages = {95-99}
}

@TechReport{MeDuBo2000,
  author =	 "Guy Melancon and I. Dutour and M. Bousquet-Melou",
  number =	 "INS-R0005",
  institution =	 "CWI - Centrum voor Wiskunde en Informatica",
  title =	 "Random generation of dags for graph drawing",
  year =	 2000,
  month =	 "March",
  url =		 "http://www.cwi.nl/ftp/CWIreports/INS/INS-R0005.ps.Z",
}  


@Article{Mosbah1996,
title={Probabilistic hyperedge replacement grammars},
author={Mohamed Mosbah},
pages={81--102},
journal=tcs,
month={28~} # may,
year=1996,
volume=159,
number=1,
}


@Article{Mosbah99:_non,
  author = 	 {Mohamed Mosbah and Nasser Saheb},
  title = 	 {Non-uniform random spanning trees on weighted graphs},
  journal = 	 tcs,
  year = 	 1999,
  volume =	 218,
  number =	 2,
  pages =	 {263--271}
}


@book{NiWi79,
	author	= "A. Nijenhuis and Herbert S. Wilf",
	title	= "Combinatorial algorithms",
	publisher = "Academic Press Inc.",
	year	= "1979"
}


@article{Pal87,
  author = {J.M. Pallo},
  title = {Generating trees with $n$ nodes and $m$ leaves},
  journal = {Int. J. Comp. Math},
  volume = {21},
  pages = {133-144},
  year = {1987}
}

@InProceedings{PeLe98,
  author =       "Marcus Peinado and Thomas Lengauer",
  title =        "Random Generation of Embedded Graphs and an Extension
                 to {Dobrushin} Uniqueness",
  pages =        "176--185",
  ISBN =         "0-89791-962-9",
  booktitle =    "Proceedings of the 30th Annual {ACM} Symposium on
                 Theory of Computing ({STOC}-98)",
  month =        may # "~23--26",
  publisher =    "ACM Press",
  address =      "New York",
  year =         "1998",
}	

@article{Pro80,
  author = {A. Proskurowski},
  title = {On the generation of binary trees},
  journal = {J. A.C.M},
  volume = {27},
  number = {1},
  year = {1980},
  pages = {1-2}
}

@Article{Propp97,
  author = 	 {J. G. Propp},
  title = 	 {Generating random elements of a finite distributive lattice},
  journal = 	 {Electronic Journal of Combinatorics},
  year = 	 1997,
  volume =	 4,
  number =	 2,
  note =	 {R15},
  html =         {http://www.combinatorics.org/Volume_4/wilftoc.html}
}


@Article{ProppW1998,
title={How to Get a Perfectly Random Sample from a Generic {Markov}
Chain and Generate a Random Spanning Tree of a Directed Graph},
author={James Gary Propp and David Bruce Wilson},
pages={170--217},
journal=jalgo,
year=1998,
month=may,
volume=27,
number=2,
preliminary={soda::WilsonP1996:448},
}

@Article{Quiroz89,
  author =       "Quiroz",
  title =        "Fast Random Generation of Binary, t-ary and Other
                 Types of Trees",
  journal =      "CLASSIF: Journal of Classification",
  volume =       "6",
  year =         "1989",
}

@article{Rem85,
	author	= "Jean-Luc R\'emy",
	title	= "Un proc\'ed\'e it\'eratif de d\'enombrement 
	           d'arbres binaires et son application \`a
                   leur g\'en\'eration al\'eatoire
                   ({F}rench) [An iterative method for counting binary trees, 
                    and application to their random generation]",
        journal	= "R. AI. R. O Informatique Th\'eorique",
        volume	= "19",
        number	= "2",
        year	= "1985",
        pages	= "179-195"
}

@Proceedings{SODA6,
title={Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete
Algorithms},
booktitle={Proceedings of the Sixth Annual ACM-SIAM Symposium on
Discrete Algorithms},
month={22--24 } # jan,
year=1995,
address={San Francisco, California},
c-organization={ACM/SIAM},
key={ACM/SIAM},
crossrefonly=1,
}

@Proceedings{STOC23,
title={Proceedings of the Twenty Third Annual ACM Symposium on Theory
of Computing},
booktitle={Proceedings of the Twenty Third Annual ACM Symposium on
Theory of Computing},
month={6--8 } # may,
year=1991,
address={New Orleans, Louisiana},
c-organization={ACM},
key={ACM},
crossrefonly=1,
}

@Proceedings{STOC28,
title={Proceedings of the Twenty-Eighth Annual ACM Symposium on
the Theory of Computing},
booktitle={Proceedings of the Twenty-Eighth Annual ACM Symposium on
the Theory of Computing},
month={22--24 } # may,
year=1996,
address={Philadelphia, Pennsylvania},
c-organization={ACM},
key={ACM},
crossrefonly=1,
}

@Article{Schaeffer97,
  author = 	 {Gilles Schaeffer},
  title = 	 "Bijective census and random generation 
                    of {E}ulerian planar maps with prescribed vertex degrees",
  journal = 	 {Electronic Journal of Combinatorics},
  year = 	 1997,
  volume =	 4,
  number =       1,
  note =	 {R20},
  annote =	 {14 pages},
  html =         {http://www.combinatorics.org/Volume_4/v4i1toc.html}
}

@InProceedings{Schaeffer99:_random,
  author = 	 {Gilles Schaeffer},
  title = 	 {Random sampling of large planar maps and convex polyhedra},
  booktitle = 	 {Proceedings of STOC'99},
  year =	 1999,
  address =	 {Atlanta},
  html =         {http://dept-info.labri.u-bordeaux.fr/\~schaeffe/cv/bibli/Polyhedra.html}
}

@PhdThesis{SchaefferThesis,
  author = 	 {Gilles Schaeffer},
  title = 	 {Conjugaison d'arbres et cartes combinatoires al\'eatoires},
  school = 	 {Universit\'e Bordeaux I},
  year = 	 1998,
  html =         {http://dept-info.labri.u-bordeaux.fr/\~schaeffe/cv/bibli/These-en.html}
}


@article{SiJe89,
  author = {Alistair Sinclair and M. R. Jerrum},
  title = {Approximate counting, uniform generation and rapidly mixing
             {M}arkov chains},
  journal = {Information and Computation},
  volume= 82,
  year = 1989,
  pages = {93-133}
}

@book{Sin92,
	author 	= "Alistair Sinclair",
	title 	= "Algorithms for Random Generation and Counting, 
			a {M}arkov {C}hain Approach",
	publisher={Birkha\"user},
	year	= "1992"
}

@article{Tin79,
	author=	"G. Tinhofer",
	title=	{On the generation of random graphs with given
		  properties and known distribution},
	journal = {Appl. Comput. Sci. Ber. Prakt. Inf.},
	volume=	"13",
	year=	"1979",
        pages = {265-296}
}

@article{Tin90,
	author=	"G. Tinhofer",
	title=	"Generating graphs uniformly at random",
	journal=	"Computing Supplementum",
	volume=	"7",
	year=	"1990",
        pages= {235-255} 
}

@Article{Vajnovski95,
  author = 	 {Vincent Vajnovski},
  title = 	 {Listing and Random Generation of Neuronal Trees Coded by Six Letters},
  journal = 	 {ACAM},
  year = 	 1995,
  volume =	 4,
  number =	 1,
  pages =	 {29--40}
}

@article{Wil77,
	author=	"Herbert S. Wilf",
	title=	"A Unified Setting for Sequencing, Ranking, And
		Selection Algorithms for Combinatorial Objects",
	journal="Advances in Mathematics",
	volume=	"24",
	year=	"1977",
	pages=	"281-291"
}


@article{Wil81,
	author=	"Herbert S. Wilf",
	title=	"The Uniform Selection of Free Trees",
	journal="Journal of Algorithms",
	volume=	"2",
	year=	"1981",
	pages=	"204-207"
}

@book{Wil89,
	author=	"Herbert S. Wilf",
	title=	"Combinatorial Algorithms : An Update",
	publisher="SIAM",
	year=	"1989"
}

@Article{Wilf1996,
title={R\'ecents d\'eveloppements et probl\`emes dans le domaine de la
g\'en\'eration al\'eatoire ({F}rench) [Recent developments and problems in the area
of random generation]},
author={Herbert S. Wilf},
pages={5--13},
journal=tcs,
month={28~} # may,
year=1996,
volume=159,
number=1,
}

@InProceedings{Wilson96,
title={Generating Random Spanning Trees More Quickly than the Cover
Time},
author={David Bruce Wilson},
pages={296--303},
crossref={STOC28},
}

@article{Wor84,
	author=	"N. C. Wormald",
	title=	"Generating random regular graphs", 
	journal="J. Algorithms",
	volume=	"5",
	year=	"1984",
	pages=	"247-280"
}

@article{Wor87,
	author=	"N. C. Wormald",
	title=	"Generating random unlabelled graphs", 
	journal="SIAM J. Comput",
	volume=	"16",
	number=	"4",
	year=	"1987",
	pages=	"717-727"
}

@article{Zim94,
  author = 	 "Paul Zimmermann",
  title = 	 "Ga{\"\i}a: a package for the random generation of
		  combinatorial structures",
  journal = 	 "MapleTech",
  volume =	 1,
  number =	 1,
  year =	 1994,
  pages =	 "38-46"
}

@Article{mcshine00:_random,
  author = "Lisa McShine",
  title = "Random sampling of labeled tournaments", 
  journal = "Electronic Journal of Combinatorics",
  year = 2000,
  volume =	 7,
  number =       1,
  note =	 {R8},
  annote =	 {19 pages},
  html =         {http://www.combinatorics.org/Volume_7/v7i1toc.html}
}