{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T06:41:04Z","timestamp":1791268864433,"version":"4.1.0"},"reference-count":34,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>We introduce a general method to count unlabeled combinatorial structures and to efficiently generate them at random. The approach is based on pointing unlabeled structures in an \u201cunbiased\u201d way so that a structure of size n gives rise to n pointed structures. We extend P\u00f3lya theory to the corresponding pointing operator and present a random sampling framework based on both the principles of Boltzmann sampling and P\u00f3lya operators. All previously known unlabeled construction principles for Boltzmann samplers are special cases of our new results. Our method is illustrated in several examples: in each case, we provide enumerative results and efficient random samplers. The approach applies to unlabeled families of plane and nonplane unrooted trees, and tree-like structures in general, but also to families of graphs (such as cacti graphs and outerplanar graphs) and families of planar maps.<\/jats:p>","DOI":"10.1137\/100790082","type":"journal-article","created":{"date-parts":[[2011,6,9]],"date-time":"2011-06-09T19:13:44Z","timestamp":1307646824000},"page":"721-769","source":"Crossref","is-referenced-by-count":23,"title":["Boltzmann Samplers, P\u00f3lya Theory, and Cycle Pointing"],"prefix":"10.1137","volume":"40","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"\u00c9ric","family":"Fusy","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mihyun","family":"Kang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefan","family":"Vigerske","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,6,9]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.37236\/1089"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"F. Bergeron, G. Labelle, and P. Leroux,\n                      Combinatorial Species and Tree-like Structures\n                      , Cambridge University Press, Cambridge, UK, 1997.","DOI":"10.1017\/CBO9781107325913"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.37236\/984"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305007303"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"B. Bollob\u00e1s,\n                      Random Graphs\n                      , 2nd ed., Cambridge University Press, Cambridge, UK, 2001.","DOI":"10.1017\/CBO9780511814068"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1006\/aama.1999.0665"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"P. Cameron,\n                      Permutation Groups\n                      , Cambridge University Press, Cambridge, UK, 1999.","DOI":"10.1017\/CBO9780511623677"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"L. Devroye,\n                      Non-Uniform Random Variate Generation\n                      , Springer-Verlag, New York, 1986.","DOI":"10.1007\/978-1-4613-8643-8"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548304006315"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"P. Flajolet and R. Sedgewick,\n                      Analytic Combinatorics\n                      , Cambridge University Press, Cambridge, UK, 2009.","DOI":"10.1017\/CBO9780511801655"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90226-7"},{"key":"R12","unstructured":"\u00c9. Fusy,\n                      Counting unrooted maps using tree-decomposition\n                      , S\u00e9m. Lothar. Combin., 54A (2005\/07), article B54A1."},{"key":"R13","doi-asserted-by":"crossref","unstructured":"\u00c9. Fusy, P. Flajolet, and C. Pivoteau,\n                      Boltzmann sampling of unlabelled structures\n                      , in Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), SIAM, Philadelphia, 2007, pp. 201\u2013211.","DOI":"10.1137\/1.9781611972979.5"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-08-00624-3"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1017\/S096354830100493X"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"F. Harary and E. M. Palmer,\n                      Graphical Enumeration\n                      , Academic Press, New York, London, 1973.","DOI":"10.1016\/B978-0-12-324245-7.50005-8"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"P. Hell and J. Ne\u0161et\u0159il,\n                      Graphs and Homomorphisms\n                      , Oxford University Press, Oxford, UK, 2004.","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/0139010"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"M. Jerrum,\n                      Uniform sampling modulo a group of symmetries using Markov chain simulation\n                      , in Expanding Graphs (Princeton, NJ, 1992), DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 10, AMS, Providence, RI, 1993, pp. 37\u201347.","DOI":"10.1090\/dimacs\/010\/04"},{"key":"R20","unstructured":"M. Jerrum and A. Sinclair,\n                      The Markov chain Monte Carlo method: An approach to approximate counting and integration\n                      , in Approximation Algorithms, D. Hochbaum, ed., PWS Publishing Company, Boston, 1997, pp. 482\u2013520."},{"key":"R21","unstructured":"D. E. Knuth,\n                      The Art of Computer Programming. Vol. 2. Seminumerical Algorithms\n                      , 3rd ed., Addison-Wesley, Reading, MA, 1998."},{"key":"R22","unstructured":"V. Liskovets,\n                      A census of non-isomorphic planar maps\n                      , in Algebraic Methods in Graph Theory, Vol. I, II (Szeged, 1978), Colloq. Math. Soc. J\u00e1nos Bolyai 25, North\u2013Holland, Amsterdam, New York, 1981, pp. 479\u2013494."},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1983-023-5"},{"key":"R24","unstructured":"B. Mohar and C. Thomassen,\n                      Graphs on Surfaces\n                      , Johns Hopkins University Press, Baltimore, MD, 2001."},{"key":"R25","unstructured":"A. Nijenhuis and H. Wilf,\n                      Combinatorial Algorithms\n                      , Academic Press, New York, 1979."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.2307\/1969046"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"C. Pivoteau, B. Salvy, and M. Soria,\n                      Boltzmann oracle for combinatorial systems\n                      , in Proceedings of the Fifth Colloquium on Mathematics and Computer Science: Algorithms, Trees, Combinatorics and Probabilities, Discrete Math. Theor. Comput Sci. Proc. AI, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2008, pp. 475\u2013488.","DOI":"10.46298\/dmtcs.3585"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1007\/BF02546665"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"G. P\u00f3lya and R. C. Read,\n                      Combinatorial Enumeration of Groups, Graphs and Chemical Compounds\n                      , Springer-Verlag, New York, 1987.","DOI":"10.1007\/978-1-4612-4664-0"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"R. C. Read,\n                      On general dissections of a polygon\n                      , Aequationes Math., 18 (1978), pp 370\u2013388.","DOI":"10.1007\/BF03031688"},{"key":"R31","unstructured":"B. Shoilekova,\n                      Unlabelled Enumeration of Cacti Graphs\n                      , manuscript."},{"key":"R32","unstructured":"N. Sloane,\n                      The On-Line Encyclopedia of Integer Sequences\n                      , http:\/\/www.research.att.com\/ + +njas\/sequences\/A000672 (2003)."},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1963-029-x"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90021-3"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100790082","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:29:34Z","timestamp":1787336974000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100790082"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/100790082"],"URL":"https:\/\/doi.org\/10.1137\/100790082","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}