{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:29:21Z","timestamp":1725488961582},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540744559"},{"type":"electronic","value":"9783540744566"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74456-6_7","type":"book-chapter","created":{"date-parts":[[2007,8,14]],"date-time":"2007-08-14T03:29:48Z","timestamp":1187062188000},"page":"56-66","source":"Crossref","is-referenced-by-count":1,"title":["Uncover Low Degree Vertices and Minimise the Mess: Independent Sets in Random Regular Graphs"],"prefix":"10.1007","author":[{"given":"William","family":"Duckworth","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michele","family":"Zito","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1-3","key":"7_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0166-218X(02)00290-1","volume":"135","author":"V.E. Alekseev","year":"2004","unstructured":"Alekseev, V.E.: Polynomial algorithm for finding the largest independent sets in graphs without forks. Discrete Applied Mathematics\u00a0135(1-3), 3\u201316 (2004)","journal-title":"Discrete Applied Mathematics"},{"key":"7_CR2","unstructured":"Assiyatun, H.: Large Subgraphs of Regular Graphs. PhD thesis, Department of Mathematics and Statistics - The University of Melbourne (2002)"},{"issue":"8","key":"7_CR3","doi-asserted-by":"publisher","first-page":"1249","DOI":"10.1016\/j.ejc.2006.05.003","volume":"27","author":"H. Assiyatun","year":"2006","unstructured":"Assiyatun, H., Wormald, N.: 3-star factors in random d-regular graphs. European Journal of Combinatorics\u00a027(8), 1249\u20131262 (2006)","journal-title":"European Journal of Combinatorics"},{"key":"7_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1007\/978-3-540-30540-8_5","volume-title":"Combinatorial Geometry and Graph Theory","author":"H. Assiyatun","year":"2005","unstructured":"Assiyatun, H.: Maximum induced matchings of random regular graphs. In: Akiyama, J., Baskoro, E.T., Kano, M. (eds.) IJCCGGT 2003. LNCS, vol.\u00a03330, pp. 44\u201357. Springer, Heidelberg (2005)"},{"issue":"1","key":"7_CR5","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. Journal of the Association for Computing Machinery\u00a041(1), 153\u2013180 (1994)","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"2","key":"7_CR6","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s002240000113","volume":"32","author":"P. Berman","year":"1999","unstructured":"Berman, P., Fujito, T.: On approximation properties of the independent set problem for low degree graphs. Theory of Computing Systems\u00a032(2), 115\u2013132 (1999)","journal-title":"Theory of Computing Systems"},{"key":"7_CR7","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1017\/S0305004100053056","volume":"80","author":"B. Bollob\u00e1s","year":"1976","unstructured":"Bollob\u00e1s, B., Erd\u0151s, P.: Cliques in random graphs. Mathematical Proceedings of the Cambridge Philosophical Society\u00a080, 419\u2013427 (1976)","journal-title":"Mathematical Proceedings of the Cambridge Philosophical Society"},{"issue":"1","key":"7_CR8","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1006\/jagm.2001.1178","volume":"41","author":"Z.-Z. Chen","year":"2001","unstructured":"Chen, Z.-Z.: Approximation algorithms for independent sets in map graphs. Journal of Algorithms\u00a041(1), 20\u201340 (2001)","journal-title":"Journal of Algorithms"},{"key":"7_CR9","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2<5::AID-RSA2>3.0.CO;2-Z","volume":"10","author":"A. Frieze","year":"1997","unstructured":"Frieze, A., McDiarmid, C.: Algorithmic theory of random graphs. Random Structures and Algorithms\u00a010, 5\u201342 (1997)","journal-title":"Random Structures and Algorithms"},{"issue":"2","key":"7_CR10","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0012-365X(90)90149-C","volume":"81","author":"A.M. Frieze","year":"1990","unstructured":"Frieze, A.M.: On the independence number of random graphs. Discrete Mathematics\u00a081(2), 171\u2013175 (1990)","journal-title":"Discrete Mathematics"},{"key":"7_CR11","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/0095-8956(92)90070-E","volume":"B 54","author":"A.M. Frieze","year":"1992","unstructured":"Frieze, A.M., \u0141uczak, T.: On the independence and chromatic number of random regular graphs. Journal of Combinatorial Theory\u00a0B 54, 123\u2013132 (1992)","journal-title":"Journal of Combinatorial Theory"},{"key":"7_CR12","unstructured":"Garey, M.R., Johnson, D.S.: Computer and Intractability, a Guide to the Theory of NP-Completeness. Freeman and Company (1979)"},{"issue":"2","key":"7_CR13","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1137\/0201013","volume":"1","author":"F. Gavril","year":"1972","unstructured":"Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum covering by cliques and maximum independent set of a chordal graph. SIAM Journal on Computing\u00a01(2), 180\u2013187 (1972)","journal-title":"SIAM Journal on Computing"},{"key":"7_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-51866-9","volume-title":"The Theory of Branching Processes","author":"T.E. Harris","year":"1963","unstructured":"Harris, T.E.: The Theory of Branching Processes. Springer, Heidelberg (1963)"},{"key":"7_CR15","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. H\u00e5stad","year":"1999","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within n\n                           1\u2009\u2212\u2009\u03b5\n                           . Acta Mathematica\u00a0182, 105\u2013142 (1999)","journal-title":"Acta Mathematica"},{"key":"7_CR16","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1997.0903","volume":"26","author":"H.B. Hunt","year":"1998","unstructured":"Hunt, H.B., Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: NC-approximation scheme for NP- and PSPACE-hard problems for geometric graphs. Journal of Algorithms\u00a026, 238\u2013274 (1998)","journal-title":"Journal of Algorithms"},{"key":"7_CR17","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032718","volume-title":"Random Graphs","author":"S. Janson","year":"2000","unstructured":"Janson, S., \u0141uczak, T., Ruci\u0144ski, A.: Random Graphs. John Wiley and Sons, Chichester (2000)"},{"key":"7_CR18","first-page":"179","volume":"23A","author":"B.D. McKay","year":"1987","unstructured":"McKay, B.D.: Independent sets in regular graphs of high girth. Ars Combinatoria\u00a023A, 179\u2013185 (1987)","journal-title":"Ars Combinatoria"},{"key":"7_CR19","doi-asserted-by":"publisher","first-page":"1217","DOI":"10.1214\/aoap\/1177004612","volume":"5","author":"N.C. Wormald","year":"1995","unstructured":"Wormald, N.C.: Differential equations for random processes and random graphs. Annals of Applied Probability\u00a05, 1217\u20131235 (1995)","journal-title":"Annals of Applied Probability"},{"key":"7_CR20","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/S0012-365X(03)00241-3","volume":"273","author":"N.C. Wormald","year":"2003","unstructured":"Wormald, N.C.: Analysis of greedy algorithms on graphs with bounded degrees. Discrete Mathematics\u00a0273, 235\u2013260 (2003)","journal-title":"Discrete Mathematics"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74456-6_7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:29:40Z","timestamp":1619504980000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74456-6_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540744559","9783540744566"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74456-6_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}