%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% %
% 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}
}