{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:55:26Z","timestamp":1725566126583},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540228943"},{"type":"electronic","value":"9783540278214"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27821-4_32","type":"book-chapter","created":{"date-parts":[[2010,9,14]],"date-time":"2010-09-14T18:54:06Z","timestamp":1284490446000},"page":"357-368","source":"Crossref","is-referenced-by-count":3,"title":["Maximum Weight Independent Sets and Matchings in Sparse Random Graphs"],"prefix":"10.1007","author":[{"given":"David","family":"Gamarnik","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomasz","family":"Nowicki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Grzegorz","family":"Swirszcz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"32_CR1","unstructured":"Aldous, A., Bandyopadhyay, A.: A survey of max-type recursive distributional equations. (preprint)"},{"key":"32_CR2","unstructured":"Aldous, D.: Some open problems, http:\/\/stat-www.berkeley.edu\/users\/aldous\/ Research\/problems.ps"},{"key":"32_CR3","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1007\/BF01192719","volume":"93","author":"D. Aldous","year":"1992","unstructured":"Aldous, D.: Asymptotics in the random assignment problem. Probab.Th. Rel.Fields\u00a093, 507\u2013534 (1992)","journal-title":"Probab.Th. Rel.Fields"},{"key":"32_CR4","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1002\/rsa.1015","volume":"18","author":"D. Aldous","year":"2001","unstructured":"Aldous, D.: The \u03b6(2) limit in the random assignment problem. Random Structures and Algorithms\u00a018, 381\u2013418 (2001)","journal-title":"Random Structures and Algorithms"},{"key":"32_CR5","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1002\/(SICI)1098-2418(199803)12:2<111::AID-RSA1>3.0.CO;2-#","volume":"12","author":"J. Aronson","year":"1998","unstructured":"Aronson, J., Pittel, B., Frieze, A.: Maximum matchings in sparse random graphs: Karp-Sipser revisited. Random Structures and Algorithms\u00a012, 11\u2013178 (1998)","journal-title":"Random Structures and Algorithms"},{"key":"32_CR6","volume-title":"Discrete Combinatorial Probability","author":"D. Aldous","year":"2003","unstructured":"Aldous, D., Steele, J.M.: The objective method: Probabilistic combinatorial optimization and local weak convergence. In: Kesten, H. (ed.) Discrete Combinatorial Probability, Springer, Heidelberg (2003)"},{"key":"32_CR7","volume-title":"Max-type recursive distributional equations","author":"A. Bandyopadhyay","year":"2003","unstructured":"Bandyopadhyay, A.: Max-type recursive distributional equations. University of California, Berkeley (2003)"},{"key":"32_CR8","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/S0195-6698(80)80030-8","volume":"1","author":"B. Bollobas","year":"1980","unstructured":"Bollobas, B.: A probabilistic proof of an asymptotic formula for the number of regular graphs. European J. Combinatorics\u00a01, 311\u2013316 (1980)","journal-title":"European J. Combinatorics"},{"issue":"2","key":"32_CR9","doi-asserted-by":"publisher","first-page":"433","DOI":"10.2307\/2043545","volume":"83","author":"B. Bollobas","year":"1981","unstructured":"Bollobas, B.: The independence ratio of regular graphs. Proc. Amer. Math. Soc.\u00a083(2), 433\u2013436 (1981)","journal-title":"Proc. Amer. Math. Soc."},{"key":"32_CR10","unstructured":"Brightwell, G.R., Winkler, P.: Gibbs extremality for the hard-core model on a Bethe lattice (2003) (preprint)"},{"key":"32_CR11","doi-asserted-by":"publisher","first-page":"649","DOI":"10.1002\/rsa.3240050504","volume":"5","author":"A. Frieze","year":"1994","unstructured":"Frieze, A., Suen, S.: On the independence number of random cubic graphs. Random Structures and Algorithms\u00a05, 649\u2013664 (1994)","journal-title":"Random Structures and Algorithms"},{"issue":"3","key":"32_CR12","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/s00440-004-0345-z","volume":"129","author":"D. Gamarnik","year":"2004","unstructured":"Gamarnik, D.: Linear phase transition in random linear constraint satisfaction problems. Probability Theory and Related Fields\u00a0129(3), 410\u2013440 (2004)","journal-title":"Probability Theory and Related Fields"},{"key":"32_CR13","doi-asserted-by":"crossref","unstructured":"Gamarnik, D., Nowicki, T., Swirscsz, G.: Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method, arXiv:math.PR\/0309441 (2003)","DOI":"10.1007\/978-3-540-27821-4_32"},{"key":"32_CR14","doi-asserted-by":"publisher","first-page":"179","DOI":"10.4153\/CMB-1982-024-9","volume":"25","author":"G.W. Hopkins","year":"1982","unstructured":"Hopkins, G.W., Staton, W.: Girth and independence ratio. Canad. Math. Bull\u00a025, 179\u2013186 (1982)","journal-title":"Canad. Math. Bull"},{"key":"32_CR15","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1016\/S0304-3975(01)00163-3","volume":"265","author":"A.K. Hartmann","year":"2001","unstructured":"Hartmann, A.K., Weigt, M.: Statistical mechanics perspective on the phase transition of vertex covering of finite-connectivity random graphs. Theoretical Computer Science\u00a0265, 199\u2013225 (2001)","journal-title":"Theoretical Computer Science"},{"key":"32_CR16","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032718","volume-title":"Random graphs","author":"S. Janson","year":"2000","unstructured":"Janson, S., Luczak, T., Rucinski, A.: Random graphs. John Wiley and Sons, Inc. Chichester (2000)"},{"key":"32_CR17","doi-asserted-by":"crossref","unstructured":"Karp, R., Sipser, M.: Maximum matchings in sparse random graphs. In: 22nd Annual Symposium on Foundations of Computer Science, pp. 364\u2013375 (1981)","DOI":"10.1109\/SFCS.1981.21"},{"key":"32_CR18","doi-asserted-by":"crossref","unstructured":"Martin, J.: Reconstruction thresholds on regular trees.(2003) (preprint)","DOI":"10.46298\/dmtcs.3325"},{"key":"32_CR19","doi-asserted-by":"crossref","unstructured":"Mossel, E.: Survey: information flow on trees (2003) (preprint)","DOI":"10.1090\/dimacs\/063\/12"},{"key":"32_CR20","doi-asserted-by":"crossref","unstructured":"Martinelli, F., Sinclair, A., Weitz, D.: The Ising model on trees: boundary conditions and mixing time. In: Proc. 44th IEEE Symposium on Foundations of Computer Science (2003)","DOI":"10.1109\/SFCS.2003.1238235"},{"key":"32_CR21","unstructured":"Rozikov, U.A., Suhov, U.M.: A hard-core model on a Cayley tree: an example of a loss network (2003) (preprint)"},{"key":"32_CR22","doi-asserted-by":"crossref","unstructured":"Steele, J.M.: Minimal spanning trees for graphs with random edge lenghts. Mathematics and Computer Science II. Algorithms, Trees, Combinatorics and Probabilities, 223\u2013246 (2002)","DOI":"10.1007\/978-3-0348-8211-8_14"},{"issue":"2","key":"32_CR23","doi-asserted-by":"publisher","first-page":"818","DOI":"10.1214\/aop\/1048516537","volume":"31","author":"M. Talagrand","year":"2003","unstructured":"Talagrand, M.: An assignment problem at high temperature. Annals of Probability\u00a031(2), 818\u2013848 (2003)","journal-title":"Annals of Probability"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27821-4_32.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,9]],"date-time":"2021-11-09T22:55:00Z","timestamp":1636498500000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27821-4_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228943","9783540278214"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27821-4_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}