{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:45:36Z","timestamp":1764783936323,"version":"3.37.3"},"reference-count":54,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,2,10]],"date-time":"2017-02-10T00:00:00Z","timestamp":1486684800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,2,10]],"date-time":"2017-02-10T00:00:00Z","timestamp":1486684800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1217423","CCF-1065125"],"award-info":[{"award-number":["CCF-1217423","CCF-1065125"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1420692","CCF-1217423"],"award-info":[{"award-number":["CCF-1420692","CCF-1217423"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1065125","CCF-1420692"],"award-info":[{"award-number":["CCF-1065125","CCF-1420692"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1122374","CCF-1217423"],"award-info":[{"award-number":["CCF-1122374","CCF-1217423"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1065125","CCF-1420692"],"award-info":[{"award-number":["CCF-1065125","CCF-1420692"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1122374","CCF-1217423"],"award-info":[{"award-number":["CCF-1122374","CCF-1217423"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1065125","CCF-1420692"],"award-info":[{"award-number":["CCF-1065125","CCF-1420692"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1536\/14"],"award-info":[{"award-number":["1536\/14"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Institute for the Promotion of Teaching Science and Technology"},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1217423","CCF-1420692"],"award-info":[{"award-number":["CCF-1217423","CCF-1420692"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1420692"],"award-info":[{"award-number":["CCF-1420692"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,2]]},"DOI":"10.1007\/s00453-017-0287-3","type":"journal-article","created":{"date-parts":[[2017,2,10]],"date-time":"2017-02-10T15:38:08Z","timestamp":1486741088000},"page":"668-697","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":22,"title":["Sublinear-Time Algorithms for Counting Star Subgraphs via Edge Sampling"],"prefix":"10.1007","volume":"80","author":[{"given":"Maryam","family":"Aliakbarpour","sequence":"first","affiliation":[]},{"given":"Amartya Shankha","family":"Biswas","sequence":"additional","affiliation":[]},{"given":"Themis","family":"Gouleakis","sequence":"additional","affiliation":[]},{"given":"John","family":"Peebles","sequence":"additional","affiliation":[]},{"given":"Ronitt","family":"Rubinfeld","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7572-2003","authenticated-orcid":false,"given":"Anak","family":"Yodpinyanee","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,2,10]]},"reference":[{"doi-asserted-by":"publisher","unstructured":"Ahn, K.J., Guha, S., McGregor, A.: Graph sketches: sparsification, spanners, and subgraphs. In: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2012, Scottsdale, AZ, USA, May 20\u201324, 2012, pp. 5\u201314 (2012). doi:\n                    10.1145\/2213556.2213560","key":"287_CR1","DOI":"10.1145\/2213556.2213560"},{"doi-asserted-by":"publisher","unstructured":"Alon, N., Dao, P., Hajirasouliha, I., Hormozdiari, F., Sahinalp, S.C.: Biomolecular network motif counting and discovery by color coding. In: Proceedings 16th International Conference on Intelligent Systems for Molecular Biology (ISMB), Toronto, Canada, July 19\u201323, 2008, pp. 241\u2013249 (2008). doi:\n                    10.1093\/bioinformatics\/btn163","key":"287_CR2","DOI":"10.1093\/bioinformatics\/btn163"},{"issue":"3","key":"287_CR3","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1006\/jcss.2001.1813","volume":"64","author":"N Alon","year":"2002","unstructured":"Alon, N., Gibbons, P.B., Matias, Y., Szegedy, M.: Tracking join and self-join sizes in limited storage. J. Comput. Syst. Sci. 64(3), 719\u2013747 (2002). doi:\n                    10.1006\/jcss.2001.1813","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"publisher","unstructured":"Alon, N., Gutner, S.: Balanced hashing, color coding and approximate counting. In: Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10\u201311, 2009, Revised Selected Papers, pp. 1\u201316 (2009). doi:\n                    10.1007\/978-3-642-11269-0_1","key":"287_CR4","DOI":"10.1007\/978-3-642-11269-0_1"},{"issue":"1","key":"287_CR5","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1006\/jcss.1997.1545","volume":"58","author":"N Alon","year":"1999","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. J. Comput. Syst. Sci. 58(1), 137\u2013147 (1999). doi:\n                    10.1006\/jcss.1997.1545","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"287_CR6","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF02523189","volume":"17","author":"N Alon","year":"1997","unstructured":"Alon, N., Yuster, R., Zwick, U.: Finding and counting given length cycles. Algorithmica 17(3), 209\u2013223 (1997). doi:\n                    10.1007\/BF02523189","journal-title":"Algorithmica"},{"issue":"2","key":"287_CR7","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1137\/100789403","volume":"26","author":"O Amini","year":"2012","unstructured":"Amini, O., Fomin, F.V., Saurabh, S.: Counting subgraphs via homomorphisms. SIAM J. Discrete Math. 26(2), 695\u2013717 (2012). doi:\n                    10.1137\/100789403","journal-title":"SIAM J. Discrete Math."},{"unstructured":"Bar-Yossef, Z., Kumar, R., Sivakumar, D.: Reductions in streaming algorithms, with an application to counting triangles in graphs. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 6\u20138, 2002, San Francisco, CA, USA., pp. 623\u2013632 (2002). \n                    http:\/\/dl.acm.org\/citation.cfm?id=545381.545464","key":"287_CR8"},{"issue":"47\u201349","key":"287_CR9","doi-asserted-by":"publisher","first-page":"5082","DOI":"10.1016\/j.tcs.2009.08.006","volume":"410","author":"T Batu","year":"2009","unstructured":"Batu, T., Berenbrink, P., Sohler, C.: A sublinear-time approximation scheme for bin packing. Theor. Comput. Sci. 410(47\u201349), 5082\u20135092 (2009). doi:\n                    10.1016\/j.tcs.2009.08.006","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"publisher","unstructured":"Becchetti, L., Boldi, P., Castillo, C., Gionis, A.: Efficient semi-streaming algorithms for local triangle counting in massive graphs. In: Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Las Vegas, Nevada, USA, August 24\u201327, 2008, pp. 16\u201324 (2008). doi:\n                    10.1145\/1401890.1401898","key":"287_CR10","DOI":"10.1145\/1401890.1401898"},{"doi-asserted-by":"crossref","unstructured":"Bhuvanagiri, L., Ganguly, S., Kesh, D., Saha, C.: Simpler algorithm for estimating frequency moments of data streams. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, pp. 708\u2013713. ACM (2006)","key":"287_CR11","DOI":"10.1145\/1109557.1109634"},{"issue":"2","key":"287_CR12","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/s00037-012-0040-x","volume":"21","author":"E Blais","year":"2012","unstructured":"Blais, E., Brody, J., Matulef, K.: Property testing lower bounds via communication complexity. Comput. Complex. 21(2), 311\u2013358 (2012). doi:\n                    10.1007\/s00037-012-0040-x","journal-title":"Comput. Complex."},{"doi-asserted-by":"publisher","unstructured":"Buriol, L.S., Frahling, G., Leonardi, S., Marchetti-Spaccamela, A., Sohler, C.: Counting triangles in data streams. In: Proceedings of the Twenty-Fifth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 26\u201328, 2006, Chicago, Illinois, USA, pp. 253\u2013262 (2006). doi:\n                    10.1145\/1142351.1142388","key":"287_CR13","DOI":"10.1145\/1142351.1142388"},{"doi-asserted-by":"publisher","unstructured":"Canonne, C.L., Rubinfeld, R.: Testing probability distributions underlying aggregated data. In: Automata, Languages, and Programming\u201441st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8\u201311, 2014, Proceedings, Part I, pp. 283\u2013295 (2014). doi:\n                    10.1007\/978-3-662-43948-7_24","key":"287_CR14","DOI":"10.1007\/978-3-662-43948-7_24"},{"unstructured":"Coppersmith, D., Kumar, R.: An improved data stream algorithm for frequency moments. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11\u201314, 2004, pp. 151\u2013156 (2004). \n                    http:\/\/dl.acm.org\/citation.cfm?id=982792.982815","key":"287_CR15"},{"issue":"3","key":"287_CR16","doi-asserted-by":"publisher","first-page":"598","DOI":"10.1137\/S0097539793247634","volume":"24","author":"RA Duke","year":"1995","unstructured":"Duke, R.A., Lefmann, H., R\u00f6dl, V.: A fast approximation algorithm for computing the frequencies of subgraphs in a given graph. SIAM J. Comput. 24(3), 598\u2013620 (1995). doi:\n                    10.1137\/S0097539793247634","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"publisher","unstructured":"Eden, T., Levi, A., Ron, D., Seshadhri, C.: Approximately counting triangles in sublinear time. In: IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17\u201320 October, 2015, pp. 614\u2013633 (2015). doi:\n                    10.1109\/FOCS.2015.44","key":"287_CR17","DOI":"10.1109\/FOCS.2015.44"},{"issue":"4","key":"287_CR18","doi-asserted-by":"publisher","first-page":"964","DOI":"10.1137\/S0097539704447304","volume":"35","author":"U Feige","year":"2006","unstructured":"Feige, U.: On sums of independent random variables with unbounded variance and estimating the average degree in a graph. SIAM J. Comput. 35(4), 964\u2013984 (2006). doi:\n                    10.1137\/S0097539704447304","journal-title":"SIAM J. Comput."},{"issue":"4","key":"287_CR19","doi-asserted-by":"publisher","first-page":"892","DOI":"10.1137\/S0097539703427203","volume":"33","author":"J Flum","year":"2004","unstructured":"Flum, J., Grohe, M.: The parameterized complexity of counting problems. SIAM J. Comput. 33(4), 892\u2013922 (2004). doi:\n                    10.1137\/S0097539703427203","journal-title":"SIAM J. Comput."},{"issue":"3","key":"287_CR20","doi-asserted-by":"publisher","first-page":"698","DOI":"10.1016\/j.jcss.2011.10.001","volume":"78","author":"FV Fomin","year":"2012","unstructured":"Fomin, F.V., Lokshtanov, D., Raman, V., Saurabh, S., Rao, B.V.R.: Faster algorithms for finding and counting subgraphs. J. Comput. Syst. Sci. 78(3), 698\u2013706 (2012). doi:\n                    10.1016\/j.jcss.2011.10.001","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"publisher","unstructured":"Getoor, L., Taskar, B., Koller, D.: Selectivity estimation using probabilistic models. In: Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data, Santa Barbara, CA, USA, May 21\u201324, 2001, pp. 461\u2013472 (2001). doi:\n                    10.1145\/375663.375727","key":"287_CR21","DOI":"10.1145\/375663.375727"},{"unstructured":"Goldreich, O.: On the communication complexity methodology for proving lower bounds on the query complexity of property testing. Electron. Colloq. Comput. Complex. (ECCC) 20, 73 (2013). \n                    http:\/\/eccc.hpi-web.de\/report\/2013\/073","key":"287_CR22"},{"issue":"4","key":"287_CR23","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1002\/rsa.20203","volume":"32","author":"O Goldreich","year":"2008","unstructured":"Goldreich, O., Ron, D.: Approximating average parameters of graphs. Random Struct. Algorithms 32(4), 473\u2013493 (2008). doi:\n                    10.1002\/rsa.20203","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"287_CR24","doi-asserted-by":"publisher","first-page":"1365","DOI":"10.1137\/100783066","volume":"25","author":"M Gonen","year":"2011","unstructured":"Gonen, M., Ron, D., Shavitt, Y.: Counting stars and other small subgraphs in sublinear-time. SIAM J. Discrete Math. 25(3), 1365\u20131411 (2011). doi:\n                    10.1137\/100783066","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"287_CR25","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1080\/15427951.2009.10390645","volume":"6","author":"M Gonen","year":"2009","unstructured":"Gonen, M., Shavitt, Y.: Approximating the number of network motifs. Internet Math. 6(3), 349\u2013372 (2009). doi:\n                    10.1080\/15427951.2009.10390645","journal-title":"Internet Math."},{"doi-asserted-by":"publisher","unstructured":"Grochow, J.A., Kellis, M.: Network motif discovery using subgraph enumeration and symmetry-breaking. In: Research in Computational Molecular Biology, 11th Annual International Conference, RECOMB 2007, Oakland, CA, USA, April 21\u201325, 2007, Proceedings, pp. 92\u2013106 (2007). doi:\n                    10.1007\/978-3-540-71681-5_7","key":"287_CR26","DOI":"10.1007\/978-3-540-71681-5_7"},{"issue":"4","key":"287_CR27","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1002\/sam.10016","volume":"1","author":"PJ Haas","year":"2009","unstructured":"Haas, P.J., Ilyas, I.F., Lohman, G.M., Markl, V.: Discovering and exploiting statistical properties for query optimization in relational databases: a survey. Stat. Anal. Data Min. 1(4), 223\u2013250 (2009). doi:\n                    10.1002\/sam.10016","journal-title":"Stat. Anal. Data Min."},{"issue":"3","key":"287_CR28","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1006\/jcss.1996.0041","volume":"52","author":"PJ Haas","year":"1996","unstructured":"Haas, P.J., Naughton, J.F., Seshadri, S., Swami, A.N.: Selectivity and cost estimation for joins based on random sampling. J. Comput. Syst. Sci. 52(3), 550\u2013569 (1996). doi:\n                    10.1006\/jcss.1996.0041","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"287_CR29","doi-asserted-by":"publisher","first-page":"239","DOI":"10.3934\/nhm.2008.3.239","volume":"3","author":"D Hales","year":"2008","unstructured":"Hales, D., Arteconi, S.: Motifs in evolving cooperative networks look like protein structure networks. NHM 3(2), 239\u2013249 (2008). doi:\n                    10.3934\/nhm.2008.3.239","journal-title":"NHM"},{"doi-asserted-by":"publisher","unstructured":"Hassidim, A., Kelner, J.A., Nguyen, H.N., Onak, K.: Local graph partitions for approximation and testing. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25\u201327, 2009, Atlanta, Georgia, USA, pp. 22\u201331 (2009). doi:\n                    10.1109\/FOCS.2009.77","key":"287_CR30","DOI":"10.1109\/FOCS.2009.77"},{"key":"287_CR31","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.0030118","author":"F Hormozdiari","year":"2007","unstructured":"Hormozdiari, F., Berenbrink, P., Przulj, N., Sahinalp, S.C.: Not all scale-free networks are born equal: The role of the seed graph in PPI network evolution. PLoS Comput Biol (2007). doi:\n                    10.1371\/journal.pcbi.0030118","journal-title":"PLoS Comput Biol"},{"doi-asserted-by":"publisher","unstructured":"Indyk, P., Woodruff, D.P.: Optimal approximations of the frequency moments of data streams. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22\u201324, 2005, pp. 202\u2013208 (2005). doi:\n                    10.1145\/1060590.1060621","key":"287_CR32","DOI":"10.1145\/1060590.1060621"},{"doi-asserted-by":"publisher","unstructured":"Kane, D.M., Mehlhorn, K., Sauerwald, T., Sun, H.: Counting arbitrary subgraphs in data streams. In: Automata, Languages, and Programming\u201439th International Colloquium, ICALP 2012, Warwick, UK, July 9\u201313, 2012, Proceedings, Part II, pp. 598\u2013609 (2012). doi:\n                    10.1007\/978-3-642-31585-5_53","key":"287_CR33","DOI":"10.1007\/978-3-642-31585-5_53"},{"issue":"11","key":"287_CR34","doi-asserted-by":"publisher","first-page":"1746","DOI":"10.1093\/bioinformatics\/bth163","volume":"20","author":"N Kashtan","year":"2004","unstructured":"Kashtan, N., Itzkovitz, S., Milo, R., Alon, U.: Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs. Bioinformatics 20(11), 1746\u20131758 (2004). doi:\n                    10.1093\/bioinformatics\/bth163","journal-title":"Bioinformatics"},{"issue":"1\u20132","key":"287_CR35","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1080\/15427951.2012.625260","volume":"8","author":"MN Kolountzakis","year":"2012","unstructured":"Kolountzakis, M.N., Miller, G.L., Peng, R., Tsourakakis, C.E.: Efficient triangle counting in large graphs via degree-based vertex partitioning. Internet Math. 8(1\u20132), 161\u2013185 (2012). doi:\n                    10.1080\/15427951.2012.625260","journal-title":"Internet Math."},{"doi-asserted-by":"publisher","unstructured":"Lee, J., Kim, D., Chung, C.: Multi-dimensional selectivity estimation using compressed histogram information. In: SIGMOD 1999, Proceedings ACM SIGMOD International Conference on Management of Data, June 1\u20133, 1999, Philadelphia, Pennsylvania, USA., pp. 205\u2013214 (1999). doi:\n                    10.1145\/304182.304200","key":"287_CR36","DOI":"10.1145\/304182.304200"},{"doi-asserted-by":"publisher","unstructured":"Manjunath, M., Mehlhorn, K., Panagiotou, K., Sun, H.: Approximate counting of cycles in streams. In: Algorithms\u2014ESA 2011\u201419th Annual European Symposium, Saarbr\u00fccken, Germany, September 5\u20139, 2011. Proceedings, pp. 677\u2013688 (2011). doi:\n                    10.1007\/978-3-642-23719-5_57","key":"287_CR37","DOI":"10.1007\/978-3-642-23719-5_57"},{"issue":"1","key":"287_CR38","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/s00778-006-0030-1","volume":"16","author":"V Markl","year":"2007","unstructured":"Markl, V., Haas, P.J., Kutsch, M., Megiddo, N., Srivastava, U., Tran, T.M.: Consistent selectivity estimation via maximum entropy. VLDB J. 16(1), 55\u201376 (2007). doi:\n                    10.1007\/s00778-006-0030-1","journal-title":"VLDB J."},{"doi-asserted-by":"publisher","unstructured":"McGregor, A., Vorotnikova, S., Vu, H.T.: Better algorithms for counting triangles in data streams. In: Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26\u2013July 01, 2016, pp. 401\u2013411 (2016). doi:\n                    10.1145\/2902251.2902283","key":"287_CR39","DOI":"10.1145\/2902251.2902283"},{"issue":"5594","key":"287_CR40","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1126\/science.298.5594.824","volume":"298","author":"R Milo","year":"2002","unstructured":"Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., Alon, U.: Network motifs: simple building blocks of complex networks. Science 298(5594), 824\u2013827 (2002)","journal-title":"Science"},{"doi-asserted-by":"publisher","unstructured":"Motwani, R., Panigrahy, R., Xu, Y.: Estimating sum by weighted sampling. In: Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland, July 9\u201313, 2007, Proceedings, pp. 53\u201364 (2007). doi:\n                    10.1007\/978-3-540-73420-8_7","key":"287_CR41","DOI":"10.1007\/978-3-540-73420-8_7"},{"key":"287_CR42","volume-title":"Randomized Algorithms","author":"R Motwani","year":"2010","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Chapman & Hall\/CRC, London (2010)"},{"doi-asserted-by":"publisher","unstructured":"Nguyen, H.N., Onak, K.: Constant-time approximation algorithms via local improvements. In: 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25\u201328, 2008, Philadelphia, PA, USA, pp. 327\u2013336 (2008). doi:\n                    10.1109\/FOCS.2008.81","key":"287_CR43","DOI":"10.1109\/FOCS.2008.81"},{"unstructured":"Onak, K., Ron, D., Rosen, M., Rubinfeld, R.: A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17\u201319, 2012, pp. 1123\u20131131 (2012).\n                    http:\/\/portal.acm.org\/citation.cfm?id=2095204&CFID=63838676&CFTOKEN=79617016","key":"287_CR44"},{"issue":"1\u20133","key":"287_CR45","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/j.tcs.2007.04.040","volume":"381","author":"M Parnas","year":"2007","unstructured":"Parnas, M., Ron, D.: Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. Theor. Comput. Sci. 381(1\u20133), 183\u2013196 (2007). doi:\n                    10.1016\/j.tcs.2007.04.040","journal-title":"Theor. Comput. Sci."},{"unstructured":"Poosala, V., Ioannidis, Y.E.: Selectivity estimation without the attribute value independence assumption. In: VLDB\u201997, Proceedings of 23rd International Conference on Very Large Data Bases, August 25\u201329, 1997, Athens, Greece, pp. 486\u2013495 (1997). \n                    http:\/\/www.vldb.org\/conf\/1997\/P486.PDF","key":"287_CR46"},{"issue":"18","key":"287_CR47","doi-asserted-by":"publisher","first-page":"3508","DOI":"10.1093\/bioinformatics\/bth436","volume":"20","author":"N Przulj","year":"2004","unstructured":"Przulj, N., Corneil, D.G., Jurisica, I.: Modeling interactome: scale-free or geometric? Bioinformatics 20(18), 3508\u20133515 (2004). doi:\n                    10.1093\/bioinformatics\/bth436","journal-title":"Bioinformatics"},{"issue":"2","key":"287_CR48","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1089\/cmb.2006.13.133","volume":"13","author":"J Scott","year":"2006","unstructured":"Scott, J., Ideker, T., Karp, R.M., Sharan, R.: Efficient algorithms for detecting signaling pathways in protein interaction networks. J. Comput. Biol. 13(2), 133\u2013144 (2006). doi:\n                    10.1089\/cmb.2006.13.133","journal-title":"J. Comput. Biol."},{"key":"287_CR49","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1186\/1471-2105-7-199","volume":"7","author":"T Shlomi","year":"2006","unstructured":"Shlomi, T., Segal, D., Ruppin, E., Sharan, R.: Qpath: a method for querying pathways in a protein-protein interaction network. BMC Bioinform. 7, 199 (2006). doi:\n                    10.1186\/1471-2105-7-199","journal-title":"BMC Bioinform."},{"doi-asserted-by":"publisher","unstructured":"Swami, A.N., Schiefer, K.B.: On the estimation of join result sizes. In: Advances in Database Technology\u2014EDBT\u201994. 4th International Conference on Extending Database Technology, Cambridge, United Kingdom, March 28\u201331, 1994, Proceedings, pp. 287\u2013300 (1994). doi:\n                    10.1007\/3-540-57818-8_58","key":"287_CR50","DOI":"10.1007\/3-540-57818-8_58"},{"issue":"4","key":"287_CR51","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1109\/TCBB.2006.51","volume":"3","author":"S Wernicke","year":"2006","unstructured":"Wernicke, S.: Efficient detection of network motifs. IEEE\/ACM Trans. Comput. Biology Bioinform. 3(4), 347\u2013359 (2006). doi:\n                    10.1109\/TCBB.2006.51","journal-title":"IEEE\/ACM Trans. Comput. Biology Bioinform."},{"issue":"6","key":"287_CR52","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.ipl.2008.11.004","volume":"109","author":"R Williams","year":"2009","unstructured":"Williams, R.: Finding paths of length k in $$\\text{ o }{}^{*} (2^{\\text{ k }})$$ time. Inf. Process. Lett. 109(6), 315\u2013318 (2009). doi:\n                    10.1016\/j.ipl.2008.11.004","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"287_CR53","doi-asserted-by":"publisher","first-page":"831","DOI":"10.1137\/09076619X","volume":"42","author":"VV Williams","year":"2013","unstructured":"Williams, V.V., Williams, R.: Finding, minimizing, and counting weighted subgraphs. SIAM J. Comput. 42(3), 831\u2013854 (2013). doi:\n                    10.1137\/09076619X","journal-title":"SIAM J. Comput."},{"issue":"4","key":"287_CR54","doi-asserted-by":"publisher","first-page":"1074","DOI":"10.1137\/110828691","volume":"41","author":"Y Yoshida","year":"2012","unstructured":"Yoshida, Y., Yamamoto, M., Ito, H.: Improved constant-time approximation algorithms for maximum matchings and other optimization problems. SIAM J. Comput. 41(4), 1074\u20131093 (2012). doi:\n                    10.1137\/110828691","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0287-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0287-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0287-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:25:23Z","timestamp":1589696723000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0287-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,2,10]]},"references-count":54,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["287"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0287-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2017,2,10]]},"assertion":[{"value":"1 February 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 January 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 February 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with Ethical Standards"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}