{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,28]],"date-time":"2023-10-28T18:04:03Z","timestamp":1698516243130},"reference-count":23,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Algebra Comput."],"published-print":{"date-parts":[[2008,3]]},"abstract":"<jats:p> We give an efficient algorithm to randomly generate finitely generated subgroups of a given size, in a finite rank free group. Here, the size of a subgroup is the number of vertices of its representation by a reduced graph such as can be obtained by the method of Stallings foldings. Our algorithm randomly generates a subgroup of a given size n, according to the uniform distribution over size n subgroups. In the process, we give estimates of the number of size n subgroups, of the average rank of size n subgroups, and of the proportion of such subgroups that have finite index. Our algorithm has average case complexity [Formula: see text] in the RAM model and [Formula: see text] in the bitcost model. <\/jats:p>","DOI":"10.1142\/s0218196708004482","type":"journal-article","created":{"date-parts":[[2008,3,20]],"date-time":"2008-03-20T05:29:16Z","timestamp":1205990956000},"page":"375-405","source":"Crossref","is-referenced-by-count":4,"title":["RANDOM GENERATION OF FINITELY GENERATED SUBGROUPS OF A FREE GROUP"],"prefix":"10.1142","volume":"18","author":[{"given":"FR\u00c9D\u00c9RIQUE","family":"BASSINO","sequence":"first","affiliation":[{"name":"Institut Gaspard Monge, Universit\u00e9 Paris-Est, Marne-la-Vall\u00e9e, 77454 Marne-la-Vall\u00e9e Cedex 2, France"}]},{"given":"CYRIL","family":"NICAUD","sequence":"additional","affiliation":[{"name":"Institut Gaspard Monge, Universit\u00e9 Paris-Est, Marne-la-Vall\u00e9e, 77454 Marne-la-Vall\u00e9e Cedex 2, France"}]},{"given":"PASCAL","family":"WEIL","sequence":"additional","affiliation":[{"name":"LaBRI, Universit\u00e9 de Bordeaux, CNRS, LaBRI, 351 cours de la Lib\u00e9ration, 33400 Talence, France"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1137\/1016082"},{"key":"rf2","first-page":"451","volume":"9","author":"Bender E. A.","journal-title":"J. London Math. Soc."},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02772626"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00323-5"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8643-8"},{"key":"rf6","volume":"12","author":"Dixon J. D.","journal-title":"Electron. J. Combin."},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548304006315"},{"key":"rf9","volume-title":"An Introduction to the Analysis of Algorithms","author":"Flajolet P.","year":"1996"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90226-7"},{"key":"rf12","volume-title":"Mathematics for the Analysis of Algorithms","author":"Greene D. H.","year":"1981"},{"key":"rf13","first-page":"67","volume":"196","author":"Hayman W. K.","journal-title":"Journal f\u00fcr die reine und angewandte Mathematik"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/298\/05115"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1006\/jabr.2001.9033"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-8693(03)00167-4"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2003.02.001"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-8965-0"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196701000498"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7643-8412-8_12"},{"key":"rf23","volume-title":"Combinatorial Algorithms","author":"Nijenhuis A.","year":"1978"},{"key":"rf24","unstructured":"A. M.\u00a0Odlyzko, Handbook of Combinatorics\u00a0II, eds. R.\u00a0Grahams, M.\u00a0Gr\u00f6tschel and A.\u00a0Lov\u00e1sz (Elsevier, 1995)\u00a0pp. 1063\u20131229."},{"key":"rf27","doi-asserted-by":"publisher","DOI":"10.1007\/BF02095993"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196706003396"},{"key":"rf29","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1388-8_16"}],"container-title":["International Journal of Algebra and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218196708004482","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T18:28:55Z","timestamp":1565116135000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218196708004482"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3]]},"references-count":23,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2008,3]]}},"alternative-id":["10.1142\/S0218196708004482"],"URL":"https:\/\/doi.org\/10.1142\/s0218196708004482","relation":{},"ISSN":["0218-1967","1793-6500"],"issn-type":[{"value":"0218-1967","type":"print"},{"value":"1793-6500","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,3]]}}}