{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:31:15Z","timestamp":1725543075256},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540369257"},{"type":"electronic","value":"9783540369264"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11809678_25","type":"book-chapter","created":{"date-parts":[[2006,8,15]],"date-time":"2006-08-15T13:41:33Z","timestamp":1155649293000},"page":"226-234","source":"Crossref","is-referenced-by-count":5,"title":["On the Threshold of Having a Linear Treewidth in Random Graphs"],"prefix":"10.1007","author":[{"given":"Yong","family":"Gao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"25_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth: Computations and Approximations","author":"T. Kloks","year":"1994","unstructured":"Kloks, T.: Treewidth: Computations and Approximations. Springer, Heidelberg (1994)"},{"key":"25_CR2","unstructured":"Bodlaender, H.L.: A tourist guide through treewidth. Technical report, Technical Report RUU-CS-92-12, Department of Computer Science, Utrecht University (1992)"},{"key":"25_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1007\/3-540-46135-3_21","volume-title":"Principles and Practice of Constraint Programming - CP 2002","author":"V. Dalmau","year":"2002","unstructured":"Dalmau, V., Kolaitis, P., Vardi, M.Y.: Constraint satisfaction, bounded treewidth, and finite-variable logics. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol.\u00a02470, pp. 310\u2013326. Springer, Heidelberg (2002)"},{"key":"25_CR4","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/S0004-3702(00)00050-3","volume":"125","author":"R. Dechter","year":"2001","unstructured":"Dechter, R., Fattah, Y.: Topological parameters for time-space tradeoff. Artificial Intelligence\u00a0125, 93\u2013118 (2001)","journal-title":"Artificial Intelligence"},{"key":"25_CR5","first-page":"331","volume-title":"Proceedings of the 12th International Joint Conference on Artificial Intelligence","author":"P. Cheeseman","year":"1991","unstructured":"Cheeseman, P., Kanefsky, B., Taylor, W.M.: Where the really hard problems are. In: Proceedings of the 12th International Joint Conference on Artificial Intelligence, pp. 331\u2013337. Morgan Kaufmann, San Francisco (1991)"},{"key":"25_CR6","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","volume-title":"Satisfiability Problem: Theory and Applications.","author":"S. Cook","year":"1997","unstructured":"Cook, S., Mitchell, D.G.: Finding hard instances of the satisfiability problem: A survey. In: Du, Gu, Pardalos (eds.) Satisfiability Problem: Theory and Applications. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a035. American Mathematical Society, Providence (1997)"},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Beame, P., Molloy, M.: A sharp threshold in proof complexity. In: ACM Symposium on Theory of Computing, pp. 337\u2013346 (2001)","DOI":"10.1145\/380752.380820"},{"key":"25_CR8","doi-asserted-by":"crossref","unstructured":"Kirousis, L., Kranakis, E.: Special issue on typical case complexity and phase transitions. Discrete Applied Mathematics\u00a0153 (2005)","DOI":"10.1016\/j.dam.2005.07.007"},{"key":"25_CR9","first-page":"17","volume":"5","author":"P. Erd\u00f6s","year":"1960","unstructured":"Erd\u00f6s, P., Renyi, A.: On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci.\u00a05, 17\u201361 (1960)","journal-title":"Publ. Math. Inst. Hungar. Acad. Sci."},{"key":"25_CR10","unstructured":"Gao, Y.: Phase Transitions and Typical-case Complexity: easy (hard) aspects of hard (easy) problem. PhD thesis, Department of Computing Science, University of Alberta, Edmonton, Canada (2005)"},{"key":"25_CR11","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814068","volume-title":"Random Graphs","author":"B. Bollobas","year":"2001","unstructured":"Bollobas, B.: Random Graphs. Cambridge University Press, Cambridge (2001)"},{"key":"25_CR12","series-title":"London Mathematical Society Lecture Note Series","first-page":"148","volume-title":"Surveys in Combinatorics","author":"C. McDiarmid","year":"1989","unstructured":"McDiarmid, C.: On the method of bounded differences. In: Surveys in Combinatorics. London Mathematical Society Lecture Note Series, vol.\u00a0141, pp. 148\u2013188. Cambridge Univ. Press, Cambridge (1989)"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11809678_25.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:26:34Z","timestamp":1619508394000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11809678_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540369257","9783540369264"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/11809678_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}