{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,25]],"date-time":"2025-04-25T13:26:04Z","timestamp":1745587564061},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642401039"},{"type":"electronic","value":"9783642401046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40104-6_27","type":"book-chapter","created":{"date-parts":[[2013,7,11]],"date-time":"2013-07-11T05:36:30Z","timestamp":1373520990000},"page":"304-315","source":"Crossref","is-referenced-by-count":10,"title":["A Dynamic Data Structure for Counting Subgraphs in Sparse Graphs"],"prefix":"10.1007","author":[{"given":"Zden\u011bk","family":"Dvo\u0159\u00e1k","sequence":"first","affiliation":[]},{"given":"Vojt\u011bch","family":"T\u016fma","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"27_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/3-540-48447-7_34","volume-title":"Algorithms and Data Structures","author":"G.S. Brodal","year":"1999","unstructured":"Brodal, G.S., Fagerberg, R.: Dynamic representations of sparse graphs. In: Dehne, F., Gupta, A., Sack, J.-R., Tamassia, R. (eds.) WADS 1999. LNCS, vol.\u00a01663, pp. 342\u2013351. Springer, Heidelberg (1999)"},{"issue":"2","key":"27_CR2","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0304-3975(91)90020-3","volume":"86","author":"M. Chrobak","year":"1991","unstructured":"Chrobak, M., Eppstein, D.: Planar orientations with low out-degree and compaction of adjacency matrices. Theoretical Computer Science\u00a086(2), 243\u2013266 (1991)","journal-title":"Theoretical Computer Science"},{"key":"27_CR3","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0304-3975(94)00097-3","volume":"141","author":"R. Downey","year":"1995","unstructured":"Downey, R., Fellows, M.: Fixed-parameter tractability and completeness. II. On completeness for W[1]. Theoretical Computer Science\u00a0141, 109\u2013131 (1995)","journal-title":"Theoretical Computer Science"},{"key":"27_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-3-642-11409-0_2","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"Z. Dvo\u0159\u00e1k","year":"2010","unstructured":"Dvo\u0159\u00e1k, Z., Kr\u00e1l\u2019, D.: Algorithms for classes of graphs with bounded expansion. In: Paul, C., Habib, M. (eds.) WG 2009. LNCS, vol.\u00a05911, pp. 17\u201332. Springer, Heidelberg (2010)"},{"key":"27_CR5","doi-asserted-by":"crossref","unstructured":"Dvo\u0159\u00e1k, Z., Kr\u00e1l\u2019, D., Thomas, R.: Deciding first-order properties for sparse graphs. In: FOCS, pp. 133\u2013142. IEEE Computer Society (2010)","DOI":"10.1109\/FOCS.2010.20"},{"key":"27_CR6","unstructured":"Dvo\u0159\u00e1k, Z., Kr\u00e1l\u2019, D., Thomas, R.: Testing first-order properties for subclasses of sparse graphs. ArXiv e-prints, 1109.5036 (January 2013)"},{"key":"27_CR7","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.tcs.2004.05.009","volume":"326","author":"F. Eisenbrand","year":"2004","unstructured":"Eisenbrand, F., Grandoni, F.: On the complexity of fixed parameter clique and dominating set. Theoretical Computer Science\u00a0326, 57\u201367 (2004)","journal-title":"Theoretical Computer Science"},{"key":"27_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.7155\/jgaa.00014","volume":"3","author":"D. Eppstein","year":"1999","unstructured":"Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. J. Graph Algorithms Appl.\u00a03, 1\u201327 (1999)","journal-title":"J. Graph Algorithms Appl."},{"key":"27_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1007\/978-3-642-17458-2_12","volume-title":"Combinatorial Optimization and Applications","author":"D. Eppstein","year":"2010","unstructured":"Eppstein, D., Goodrich, M.T., Strash, D., Trott, L.: Extended dynamic subgraph statistics using h-index parameterized data structures. In: Wu, W., Daescu, O. (eds.) COCOA 2010, Part I. LNCS, vol.\u00a06508, pp. 128\u2013141. Springer, Heidelberg (2010)"},{"key":"27_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1007\/978-3-642-03367-4_25","volume-title":"Algorithms and Data Structures","author":"D. Eppstein","year":"2009","unstructured":"Eppstein, D., Spiro, E.S.: The h-index of a graph and its application to dynamic subgraph statistics. In: Dehne, F., Gavrilova, M., Sack, J.-R., T\u00f3th, C.D. (eds.) WADS 2009. LNCS, vol.\u00a05664, pp. 278\u2013289. Springer, Heidelberg (2009)"},{"key":"27_CR11","doi-asserted-by":"publisher","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\u00a048, 1184\u20131206 (2001)","journal-title":"J. ACM"},{"key":"27_CR12","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/S0020-0190(00)00047-8","volume":"74","author":"T. Kloks","year":"2000","unstructured":"Kloks, T., Kratsch, D., M\u00fcller, H.: Finding and counting small induced subgraphs efficiently. Information Processing Letters\u00a074, 115\u2013121 (2000)","journal-title":"Information Processing Letters"},{"key":"27_CR13","first-page":"257","volume":"6","author":"T. Milenkovi\u00e6","year":"2008","unstructured":"Milenkovi\u00e6, T., Pr\u017eulj, N.: Uncovering biological network function via graphlet degree signatures. Cancer Informatics\u00a06, 257 (2008)","journal-title":"Cancer Informatics"},{"key":"27_CR14","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Linear time low tree-width partitions and algorithmic consequences. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC 2006, pp. 391\u2013400. ACM (2006)","DOI":"10.1145\/1132516.1132575"},{"key":"27_CR15","doi-asserted-by":"publisher","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., Ossona de Mendez, P.: Grad and classes with bounded expansion I. Decomposition. European J. Combin.\u00a029, 760\u2013776 (2008)","journal-title":"European J. Combin."},{"key":"27_CR16","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/978-3-540-85221-6_13","volume":"19","author":"J. Ne\u0161et\u0159il","year":"2008","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Structural properties of sparse graphs. Bolyai Society Mathematical Studies\u00a019, 369\u2013426 (2008)","journal-title":"Bolyai Society Mathematical Studies"},{"key":"27_CR17","doi-asserted-by":"publisher","first-page":"868","DOI":"10.2178\/jsl\/1278682204","volume":"75","author":"J. Ne\u0161et\u0159il","year":"2010","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: First order properties on nowhere dense structures. J. Symbolic Logic\u00a075, 868\u2013887 (2010)","journal-title":"J. Symbolic Logic"},{"key":"27_CR18","doi-asserted-by":"publisher","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., Ossona de Mendez, P., Wood, D.: Characterisations and examples of graph classes with bounded expansion. Eur. J. Comb.\u00a033, 350\u2013373 (2012)","journal-title":"Eur. J. Comb."},{"key":"27_CR19","first-page":"415","volume":"26","author":"J. Ne\u0161et\u0159il","year":"1985","unstructured":"Ne\u0161et\u0159il, J., Poljak, S.: Complexity of the subgraph problem. Comment. Math. Univ. Carol.\u00a026, 415\u2013420 (1985)","journal-title":"Comment. Math. Univ. Carol."},{"issue":"2","key":"27_CR20","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/j.socnet.2006.08.004","volume":"29","author":"G. Robins","year":"2007","unstructured":"Robins, G., Morris, M.: Advances in exponential random graph (p\n                \u2009\u2217\u2009) models. Social Networks\u00a029(2), 169\u2013172 (2007)","journal-title":"Social Networks"},{"key":"27_CR21","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1006\/jctb.1994.1052","volume":"62","author":"C. Thomassen","year":"1994","unstructured":"Thomassen, C.: Five-coloring graphs on the torus. J. Combin. Theory, Ser.\u00a0B\u00a062, 11\u201333 (1994)","journal-title":"J. Combin. Theory, Ser.\u00a0B"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40104-6_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T18:41:17Z","timestamp":1557945677000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40104-6_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642401039","9783642401046"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40104-6_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}