{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T02:50:39Z","timestamp":1725936639646},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319731162"},{"type":"electronic","value":"9783319731179"}],"license":[{"start":{"date-parts":[[2017,12,22]],"date-time":"2017-12-22T00:00:00Z","timestamp":1513900800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-73117-9_9","type":"book-chapter","created":{"date-parts":[[2017,12,21]],"date-time":"2017-12-21T11:45:34Z","timestamp":1513856734000},"page":"125-136","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Local Structure Theorems for Erd\u0151s\u2013R\u00e9nyi Graphs and Their Algorithmic Applications"],"prefix":"10.1007","author":[{"given":"Jan","family":"Dreier","sequence":"first","affiliation":[]},{"given":"Philipp","family":"Kuinke","sequence":"additional","affiliation":[]},{"given":"Ba Le","family":"Xuan","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Rossmanith","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,12,22]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814068","volume-title":"Random Graphs","author":"B Bollob\u00e1s","year":"2001","unstructured":"Bollob\u00e1s, B.: Random Graphs, 2nd edn. Cambridge University Press, Cambridge (2001)","edition":"2"},{"key":"9_CR2","first-page":"290","volume":"6","author":"P Erd\u0151s","year":"1959","unstructured":"Erd\u0151s, P., R\u00e9nyi, A.: On random graphs. Publ. Math. 6, 290\u2013297 (1959)","journal-title":"Publ. Math."},{"issue":"1","key":"9_CR3","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1017\/S0022481200051756","volume":"41","author":"R Fagin","year":"1976","unstructured":"Fagin, R.: Probabilities on finite models. J. Symb. Log. 41(1), 50\u201358 (1976)","journal-title":"J. Symb. Log."},{"key":"9_CR4","unstructured":"Grohe, M.: Logic, graphs, and algorithms (2007)"},{"key":"9_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/3-540-36494-3_43","volume-title":"STACS 2003","author":"A Coja-Oghlan","year":"2003","unstructured":"Coja-Oghlan, A., Taraz, A.: Colouring random graphs in expected polynomial time. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 487\u2013498. Springer, Heidelberg (2003). \nhttps:\/\/doi.org\/10.1007\/3-540-36494-3_43"},{"key":"9_CR6","doi-asserted-by":"crossref","unstructured":"Dawar, A., Grohe, M., Kreutzer, S.: Locally excluding a minor. In: 22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007), pp. 270\u2013279, July 2007","DOI":"10.1109\/LICS.2007.31"},{"issue":"6","key":"9_CR7","doi-asserted-by":"crossref","first-page":"716","DOI":"10.1145\/602220.602222","volume":"49","author":"J Flum","year":"2002","unstructured":"Flum, J., Frick, M., Grohe, M.: Query evaluation via tree-decompositions. J. ACM 49(6), 716\u2013752 (2002)","journal-title":"J. ACM"},{"issue":"4\u20135","key":"9_CR8","doi-asserted-by":"crossref","first-page":"566","DOI":"10.1016\/j.dam.2011.10.013","volume":"160","author":"Y Gao","year":"2012","unstructured":"Gao, Y.: Treewidth of Erd\u0151s\u2013R\u00e9nyi random graphs, random intersection graphs, and scale-free random graphs. Discrete Appl. Math. 160(4\u20135), 566\u2013578 (2012)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"9_CR9","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1016\/j.ejc.2006.07.013","volume":"29","author":"J Ne\u0161et\u0159il","year":"2008","unstructured":"Ne\u0161et\u0159il, J., de Mendez, P.O.: Grad and classes with bounded expansion I. Decompositions. Eur. J. Comb. 29(3), 760\u2013776 (2008)","journal-title":"Eur. J. Comb."},{"issue":"5","key":"9_CR10","doi-asserted-by":"crossref","first-page":"36:1","DOI":"10.1145\/2499483","volume":"60","author":"Z Dvo\u0159\u00e1k","year":"2013","unstructured":"Dvo\u0159\u00e1k, Z., Kr\u00e1\u00ce, D., Thomas, R.: Testing first-order properties for subclasses of sparse graphs. J. ACM 60(5), 36:1\u201336:24 (2013)","journal-title":"J. ACM"},{"key":"9_CR11","doi-asserted-by":"crossref","unstructured":"Grohe, M., Kreutzer, S., Siebertz, S.: Deciding first-order properties of nowhere dense graphs. In: Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC 2014, pp. 89\u201398. ACM, New York (2014)","DOI":"10.1145\/2591796.2591851"},{"issue":"3","key":"9_CR12","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1016\/j.ejc.2011.09.008","volume":"33","author":"J Ne\u0161et\u0159il","year":"2012","unstructured":"Ne\u0161et\u0159il, J., de Mendez, P.O., Wood, D.R.: Characterisations and examples of graph classes with bounded expansion. Eur. J. Comb. 33(3), 350\u2013373 (2012). Topological and Geometric Graph Theory","journal-title":"Eur. J. Comb."},{"key":"9_CR13","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1016\/j.tcs.2015.01.042","volume":"576","author":"N Fountoulakis","year":"2015","unstructured":"Fountoulakis, N., Friedrich, T., Hermelin, D.: On the average-case complexity of parameterized clique. Theoret. Comput. Sci. 576, 18\u201329 (2015)","journal-title":"Theoret. Comput. Sci."},{"issue":"6","key":"9_CR14","doi-asserted-by":"crossref","first-page":"1184","DOI":"10.1145\/504794.504798","volume":"48","author":"M Frick","year":"2001","unstructured":"Frick, M., Grohe, M.: Deciding first-order properties of locally tree-decomposable structures. J. ACM 48(6), 1184\u20131206 (2001)","journal-title":"J. ACM"},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"Dawar, A., Grohe, M., Kreutzer, S.: Locally excluding a minor. In: Proceedings of the 22nd IEEE Symposium on Logic in Computer Science (LICS 2007), Wroclaw, Poland, 10\u201312 July 2007, pp. 270\u2013279. IEEE Computer Society (2007)","DOI":"10.1109\/LICS.2007.31"},{"key":"9_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1007\/3-540-44693-1_2","volume-title":"STACS 2001","author":"M Grohe","year":"2001","unstructured":"Grohe, M.: Generalized model-checking problems for first-order logic. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol. 2010, pp. 12\u201326. Springer, Heidelberg (2001). \nhttps:\/\/doi.org\/10.1007\/3-540-44693-1_2"},{"issue":"5439","key":"9_CR17","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"AL Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509\u2013512 (1999). American Association for the Advancement of Science","journal-title":"Science"},{"key":"9_CR18","doi-asserted-by":"crossref","first-page":"058701","DOI":"10.1103\/PhysRevLett.90.058701","volume":"90","author":"R Cohen","year":"2003","unstructured":"Cohen, R., Havlin, S.: Scale-free networks are ultrasmall. Phys. Rev. Lett. 90, 058701 (2003)","journal-title":"Phys. Rev. Lett."},{"issue":"17","key":"9_CR19","doi-asserted-by":"crossref","first-page":"175101","DOI":"10.1088\/1751-8113\/44\/17\/175101","volume":"44","author":"MH Kamrul","year":"2011","unstructured":"Kamrul, M.H., Hassan, M.Z., Pavel, N.I.: Dynamic scaling, data-collapse and self-similarity in Barab\u00e1si\u2013Albert networks. J. Phys. A: Math. Theoret. 44(17), 175101 (2011)","journal-title":"J. Phys. A: Math. Theoret."},{"key":"9_CR20","doi-asserted-by":"crossref","first-page":"057102","DOI":"10.1103\/PhysRevE.65.057102","volume":"65","author":"K Klemm","year":"2002","unstructured":"Klemm, K., Egu\u00edluz, V.M.: Growing scale-free networks with small-world behavior. Phys. Rev. E 65, 057102 (2002)","journal-title":"Phys. Rev. E"},{"key":"9_CR21","unstructured":"Demaine, E.D., Reidl, F., Rossmanith, P., Villaamil, F.S., Sikdar, S., Sullivan, B.D.: Structural sparsity of complex networks: random graph models and linear algorithms. CoRR abs\/1406.2587 (2014)"},{"key":"9_CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-14279-6","volume-title":"Graph Theory","author":"R Diestel","year":"2010","unstructured":"Diestel, R.: Graph Theory. Springer, Berlin (2010)"},{"key":"9_CR23","volume-title":"Sparsity: Graphs, Structures, and Algorithms","author":"J Ne\u0161et\u0159il","year":"2014","unstructured":"Ne\u0161et\u0159il, J., de Mendez, P.O.: Sparsity: Graphs, Structures, and Algorithms. Springer, Berlin (2014)"},{"issue":"4","key":"9_CR24","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"key":"9_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/11847250_20","volume-title":"Parameterized and Exact Computation","author":"J Chen","year":"2006","unstructured":"Chen, J., Kanj, I.A., Meng, J., Xia, G., Zhang, F.: On the effective enumerability of NP problems. In: Bodlaender, H.L., Langston, M.A. (eds.) IWPEC 2006. LNCS, vol. 4169, pp. 215\u2013226. Springer, Heidelberg (2006). \nhttps:\/\/doi.org\/10.1007\/11847250_20"},{"issue":"3","key":"9_CR26","doi-asserted-by":"crossref","first-page":"777","DOI":"10.1016\/j.ejc.2006.07.014","volume":"29","author":"J Ne\u0161et\u0159il","year":"2008","unstructured":"Ne\u0161et\u0159il, J., de Mendez, P.O.: Grad and classes with bounded expansion II. Algorithmic aspects. Eur. J. Comb. 29(3), 777\u2013791 (2008)","journal-title":"Eur. J. Comb."},{"key":"9_CR27","volume-title":"Parameterized Complexity","author":"RG Downey","year":"2012","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (2012)"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2018: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-73117-9_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,12,21]],"date-time":"2017-12-21T11:48:56Z","timestamp":1513856936000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-73117-9_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,22]]},"ISBN":["9783319731162","9783319731179"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-73117-9_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017,12,22]]}}}