{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T18:58:29Z","timestamp":1648839509312},"reference-count":9,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2010,8,24]],"date-time":"2010-08-24T00:00:00Z","timestamp":1282608000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2011,3]]},"abstract":"<jats:p>We consider the following process for generating large random cubic graphs. Starting with a given graph, repeatedly add edges that join the midpoints of two randomly chosen edges. We show that the growing graph asymptotically almost surely has logarithmic diameter. This process is motivated by a particular type of peer-to-peer network. Our method extends to similar processes that generate regular graphs of higher degree.<\/jats:p>","DOI":"10.1017\/s096354831000026x","type":"journal-article","created":{"date-parts":[[2010,8,24]],"date-time":"2010-08-24T10:40:19Z","timestamp":1282646419000},"page":"239-248","source":"Crossref","is-referenced-by-count":0,"title":["Pegging Graphs Yields a Small Diameter"],"prefix":"10.1017","volume":"20","author":[{"given":"STEFANIE","family":"GERKE","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ANGELIKA","family":"STEGER","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"NICHOLAS","family":"WORMALD","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2010,8,24]]},"reference":[{"key":"S096354831000026X_ref7","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721335.010"},{"key":"S096354831000026X_ref2","volume-title":"Proc. International Conference on Advances in Infrastructures: SSGRR 2003w","author":"Bourassa","year":"2003"},{"key":"S096354831000026X_ref1","doi-asserted-by":"publisher","DOI":"10.1137\/0401033"},{"key":"S096354831000026X_ref8","first-page":"73","volume-title":"Lectures on Approximation and Randomized Algorithms","author":"Wormald","year":"1999"},{"key":"S096354831000026X_ref3","unstructured":"[3] Cooper C. , Dyer M. and Greenhill C. (2005) Sampling regular graphs and a peer-to-peer network. In Proc. Sixteenth Annual ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 980\u2013988."},{"key":"S096354831000026X_ref9","first-page":"817","volume-title":"Handbook of Graph Theory","author":"Wormald","year":"2004"},{"key":"S096354831000026X_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20253"},{"key":"S096354831000026X_ref6","unstructured":"[6] Sanwalani V. and Wormald N. The diameter of random regular graphs. In preparation."},{"key":"S096354831000026X_ref4","unstructured":"[4] Gao P. Connectivity of random regular graphs generated by the pegging algorithm. J. Graph Theory, to appear."}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096354831000026X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T19:17:42Z","timestamp":1556392662000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096354831000026X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,8,24]]},"references-count":9,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,3]]}},"alternative-id":["S096354831000026X"],"URL":"https:\/\/doi.org\/10.1017\/s096354831000026x","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,8,24]]}}}