skip to main content
10.5555/1283383.1283421acmconferencesArticle/Chapter ViewAbstractPublication PagessodaConference Proceedingsconference-collections
Article

An unbiased pointing operator for unlabeled structures, with applications to counting and sampling

Published: 07 January 2007 Publication History

Abstract

We introduce a general method to count and randomly sample unlabeled combinatorial structures. The approach is based on pointing unlabeled structures in an "unbiased" way, i.e., in such a way that a structure of size n gives rise to n pointed structures. We develop a specific Pólya theory for the corresponding pointing operator, and present a sampling framework relying both on the principles of Boltzmann sampling and on Pólya operators. Our method is illustrated on several examples: in each case, we provide enumerative results and efficient random samplers. The approach applies to unlabeled families of plane and non-plane unrooted trees, and tree-like structures in general, but also to cactus graphs, outerplanar graphs, RNA secondary structures, and classes of planar maps.

References

[1]
J. P. Bell, S. N. Burris, and K. A. Yeats. Counting rooted trees: The universal law t(n) ~ cp-nn -3/2. http://arxiv.org/abs/math.CO/0512432, 2005.
[2]
F. Bergeron, G. Labelle, and P. Leroux. Combinatorial Species and Tree-like Structures. Cambridge University Press, 1997.
[3]
M. Bodirsky, É. Fusy, M. Kang, and S. Vigerske. Enumeration of unlabeled outerplanar graphs. Submitted, 2006.
[4]
M. Bodirsky and M. Kang. Generating outerplanar graphs uniformly at random. Comb. Prob. and Computing, 15:333--343, 2006.
[5]
P. Cameron. Permutation groups. Cambridge University Press, 1999.
[6]
P. Duchon, P. Flajolet, G. Louchard, and G. Schaeffer. Random sampling from Boltzmann principles. In ICALP'02, LNCS, pages 501--513, 2002.
[7]
P. Flajolet and R. Sedgewick. Analytic Combinatorics. 2006. Book in preparation: available at http://algo.inria.fr/flajolet/Publications/books.html.
[8]
P. Flajolet, P. Zimmerman, and B. Van Cutsem. A calculus for the random generation of labelled combinatorial structures. Theoretical Computer Science, 132(1--2):1--35, 1994.
[9]
É. Fusy. Counting unrooted maps using tree-decomposition. In Proceedings of FPSAC, 2005.
[10]
É. Fusy, P. Flajolet, and C. Pivoteau. Boltzmann sampling of unlabelled structures, 2006. Forthcoming.
[11]
F. Harary and E. M. Palmer. Graphical Enumeration. Academic Press, New York and London, 1973.
[12]
P. Hell and J. Nešetřil. Graphs and Homomorphisms. Oxford University Press, 2004.
[13]
J. A. Howell, T. F. Smith, and M. S. Waterman. Computation of generating functions for biological molecules. SIAM J. Appl. Math., 39:119--133, 1980.
[14]
M. Jerrum. Uniform sampling modulo a group of symmetries using markov chain simulation. Technical Report ECS-LFCS-94-288, Univ. Edinburgh, 1994.
[15]
V. Liskovets. A census of non-isomorphic planar maps. In Coll. Math. Soc. J. Bolyai, Proc. Conf. Algebr. Meth. in Graph Th., volume 25:2, pages 479--494, 1981.
[16]
A. Nijenhuis and H. Wilf. Combinatorial algorithms. Academic Press Inc., 1979.
[17]
Otter. The number of trees. Annals of Math., 49:583--599, 1948.
[18]
N. Sloane. A000602: Number of n-node unrooted quartic trees. http://www.research.att.com/~njas/sequences/A000602, 2003.
[19]
W. T. Tutte. A census of planar maps. Canad. J. Math., 15:249--271, 1963.
[20]
H. S. Wilf. The uniform selection of free trees. J. Algorithms, 2(2):204--207, 1981.

Cited By

View all
  • (2013)Asymptotic analysis and random sampling of digitally convex polyominoesProceedings of the 17th IAPR international conference on Discrete Geometry for Computer Imagery10.1007/978-3-642-37067-0_9(95-106)Online publication date: 20-Mar-2013
  • (2012)On the diversity of pattern distributions in rational languageProceedings of the Meeting on Analytic Algorithmics and Combinatorics10.5555/2790395.2790408(107-115)Online publication date: 16-Jan-2012
  • (2011)Lambda terms of bounded unary heightProceedings of the Meeting on Analytic Algorithmics and Combinatorics10.5555/2790409.2790412(23-32)Online publication date: 22-Jan-2011
  1. An unbiased pointing operator for unlabeled structures, with applications to counting and sampling

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms
      January 2007
      1322 pages
      ISBN:9780898716245
      • Conference Chair:
      • Harold Gabow

      Sponsors

      Publisher

      Society for Industrial and Applied Mathematics

      United States

      Publication History

      Published: 07 January 2007

      Check for updates

      Qualifiers

      • Article

      Acceptance Rates

      SODA '07 Paper Acceptance Rate 139 of 382 submissions, 36%;
      Overall Acceptance Rate 411 of 1,322 submissions, 31%

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)5
      • Downloads (Last 6 weeks)1
      Reflects downloads up to 19 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2013)Asymptotic analysis and random sampling of digitally convex polyominoesProceedings of the 17th IAPR international conference on Discrete Geometry for Computer Imagery10.1007/978-3-642-37067-0_9(95-106)Online publication date: 20-Mar-2013
      • (2012)On the diversity of pattern distributions in rational languageProceedings of the Meeting on Analytic Algorithmics and Combinatorics10.5555/2790395.2790408(107-115)Online publication date: 16-Jan-2012
      • (2011)Lambda terms of bounded unary heightProceedings of the Meeting on Analytic Algorithmics and Combinatorics10.5555/2790409.2790412(23-32)Online publication date: 22-Jan-2011

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media