{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:26Z","timestamp":1740109286408,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2019,11,14]],"date-time":"2019-11-14T00:00:00Z","timestamp":1573689600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,11,14]],"date-time":"2019-11-14T00:00:00Z","timestamp":1573689600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["24300002"],"award-info":[{"award-number":["24300002"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,5]]},"DOI":"10.1007\/s00453-019-00645-x","type":"journal-article","created":{"date-parts":[[2019,11,14]],"date-time":"2019-11-14T13:02:20Z","timestamp":1573736540000},"page":"1329-1345","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An Analysis of Budgeted Parallel Search on Conditional Galton\u2013Watson Trees"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2977-2795","authenticated-orcid":false,"given":"David","family":"Avis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luc","family":"Devroye","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,11,14]]},"reference":[{"key":"645_CR1","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1017\/CBO9780511662980.003","volume-title":"Stochastic Analysis","author":"D. Aldous","year":"1991","unstructured":"Aldous, D.: The continuum random tree. II. An overview. In: Stochastic Analysis (Durham, 1990), vol.\u00a0167, pp. 23\u201370, Cambridge University Press, Cambridge (1991)"},{"key":"645_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1214\/aop\/1176990534","volume":"19","author":"D Aldous","year":"1991","unstructured":"Aldous, D.: The continuum random tree. I. Ann. Probab. 19, 1\u201328 (1991)","journal-title":"Ann. Probab."},{"key":"645_CR3","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1214\/aoap\/1177005936","volume":"1","author":"D Aldous","year":"1991","unstructured":"Aldous, D.: Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab. 1, 228\u2013266 (1991)","journal-title":"Ann. Appl. Probab."},{"key":"645_CR4","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1214\/aop\/1176989404","volume":"21","author":"D Aldous","year":"1993","unstructured":"Aldous, D.: The continuum random tree. III. Ann. Probab. 21, 248\u2013289 (1993)","journal-title":"Ann. Probab."},{"key":"645_CR5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-65371-1","volume-title":"Branching Processes","author":"KB Athreya","year":"1972","unstructured":"Athreya, K.B., Ney, P.E.: Branching Processes. Springer, Berlin (1972)"},{"key":"645_CR6","unstructured":"Avis, D., Jordan, C.: mplrs: a scaleable parallel vertex\/facet enumeration code. arXiv:1511.06487 (2015)"},{"key":"645_CR7","unstructured":"Avis, D., Jordan, C.: A parallel framework for reverse search using mts. arXiv:1610.07735 (2016)"},{"key":"645_CR8","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1023\/A:1007862612753","volume":"13","author":"J Bennies","year":"2000","unstructured":"Bennies, J., Kersting, G.: A random walk approach to Galton\u2013Watson trees. J. Theor. Probab. 13, 777\u2013803 (2000)","journal-title":"J. Theor. Probab."},{"key":"645_CR9","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1145\/324133.324234","volume":"46","author":"N Blumofe","year":"1999","unstructured":"Blumofe, N., Leiserson, C.: Scheduling multithreaded computations by work stealing. J. ACM 46, 720\u2013748 (1999)","journal-title":"J. ACM"},{"key":"645_CR10","doi-asserted-by":"publisher","first-page":"996","DOI":"10.1214\/aop\/1048516543","volume":"31","author":"T Duquesne","year":"2003","unstructured":"Duquesne, T.: A limit theorem for the contour process of conditioned Galton\u2013Watson trees. Ann. Probab. 31, 996\u20131027 (2003)","journal-title":"Ann. Probab."},{"key":"645_CR11","doi-asserted-by":"publisher","first-page":"682","DOI":"10.2307\/3212112","volume":"6","author":"M Dwass","year":"1969","unstructured":"Dwass, M.: The total progeny in a branching process. J. Appl. Probab. 6, 682\u2013686 (1969)","journal-title":"J. Appl. Probab."},{"key":"645_CR12","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0022-0000(82)90004-6","volume":"25","author":"P Flajolet","year":"1982","unstructured":"Flajolet, P., Odlyzko, A.: The average height of binary trees and other simple trees. J. Comput. Syst. Sci. 25, 171\u2013213 (1982)","journal-title":"J. Comput. Syst. Sci."},{"key":"645_CR13","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/BF02430364","volume":"1","author":"JN Hooker","year":"1995","unstructured":"Hooker, J.N.: Testing heuristics: we have it all wrong. J. Heuristics 1, 33\u201342 (1995)","journal-title":"J. Heuristics"},{"key":"645_CR14","volume-title":"Diffusion Processes and Their Sample Paths","author":"K Ito","year":"1974","unstructured":"Ito, K., McKean, H.P.: Diffusion Processes and Their Sample Paths. Springer, Berlin (1974)"},{"key":"645_CR15","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1214\/11-PS188","volume":"9","author":"S Janson","year":"2012","unstructured":"Janson, S.: Simply generated trees, conditioned Galton\u2013Watson trees, random allocations and condensation. Probab. Surv. 9, 103\u2013252 (2012)","journal-title":"Probab. Surv."},{"key":"645_CR16","doi-asserted-by":"publisher","first-page":"800","DOI":"10.2307\/3212730","volume":"12","author":"DP Kennedy","year":"1975","unstructured":"Kennedy, D.P.: The Galton\u2013Watson process conditioned on the total progeny. J. Appl. Probab. 12, 800\u2013806 (1975)","journal-title":"J. Appl. Probab."},{"key":"645_CR17","doi-asserted-by":"publisher","first-page":"371","DOI":"10.2307\/3212843","volume":"13","author":"DP Kennedy","year":"1976","unstructured":"Kennedy, D.P.: The distribution of the maximum Brownian excursion. J. Appl. Probab. 13, 371\u2013376 (1976)","journal-title":"J. Appl. Probab."},{"key":"645_CR18","unstructured":"Kolchin, V.F.: Branching processes and random trees.In: Problems in Cybernetics, Combinatorial Analysis and Graph Theory (in Russian), pp.\u00a085\u201397, Nauka, Moscow (1980)"},{"key":"645_CR19","volume-title":"Random Mappings","author":"VF Kolchin","year":"1986","unstructured":"Kolchin, V.F.: Random Mappings. Optimization Software Inc., New York (1986)"},{"key":"645_CR20","doi-asserted-by":"crossref","unstructured":"Le Gall, J.-F.: Marches al\u00e9atoires, mouvement Brownien etprocessus de branchement.In: S\u00e9minaire de Probabilit\u00e9sXXIII, edited by Az\u00e9ma, J., Meyer, P.A., Yor, M. vol. 1372, pp. 258\u2013274. Lecture Notes in Mathematics, Springer-Verlag, Berlin (1989)","DOI":"10.1007\/BFb0083978"},{"key":"645_CR21","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1214\/154957805100000140","volume":"2","author":"J-F Le Gall","year":"2005","unstructured":"Le Gall, J.-F.: Random trees and applications. Probab. Surv. 2, 245\u2013311 (2005)","journal-title":"Probab. Surv."},{"key":"645_CR22","doi-asserted-by":"publisher","first-page":"1655","DOI":"10.1214\/aop\/1055425793","volume":"31","author":"JF Marckert","year":"2003","unstructured":"Marckert, J.F., Mokkadem, A.: The depth first processes of Galton\u2013Watson trees converge to the same Brownian excursion. Ann. Probab. 31, 1655\u20131678 (2003)","journal-title":"Ann. Probab."},{"key":"645_CR23","volume-title":"Patterns for Parallel Programming","author":"T Mattson","year":"2004","unstructured":"Mattson, T., Saunders, B., Massingill, B.: Patterns for Parallel Programming. Addison-Wesley, Boston (2004)"},{"key":"645_CR24","first-page":"8:1","volume":"2","author":"C McCreesh","year":"2015","unstructured":"McCreesh, C., Prosser, P.: The shape of the search tree for the maximum clique problem and the implications for parallel branch and bound. ACM Trans. Parallel Process. 2, 8:1\u20138:27 (2015)","journal-title":"ACM Trans. Parallel Process."},{"key":"645_CR25","doi-asserted-by":"publisher","first-page":"997","DOI":"10.4153\/CJM-1978-085-0","volume":"30","author":"A Meir","year":"1978","unstructured":"Meir, A., Moon, J.W.: On the altitude of nodes in random trees. Can. J. Math. 30, 997\u20131015 (1978)","journal-title":"Can. J. Math."},{"key":"645_CR26","volume-title":"Counting Labelled Trees","author":"JW Moon","year":"1970","unstructured":"Moon, J.W.: Counting Labelled Trees. Canadian Mathematical Congress, Montreal (1970)"},{"key":"645_CR27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-65809-9","volume-title":"Sums of Independent Random Variables","author":"VV Petrov","year":"1975","unstructured":"Petrov, V.V.: Sums of Independent Random Variables. Springer, Berlin (1975)"},{"key":"645_CR28","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1017\/S1446788700004432","volume":"7","author":"A R\u00e9nyi","year":"1967","unstructured":"R\u00e9nyi, A., Szekeres, G.: On the height of trees. J. Aust. Math. Soc. 7, 497\u2013507 (1967)","journal-title":"J. Aust. Math. Soc."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00645-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00645-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00645-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T00:16:21Z","timestamp":1605226581000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00645-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,14]]},"references-count":28,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["645"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00645-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,11,14]]},"assertion":[{"value":"13 April 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 October 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 November 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}