{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T18:02:26Z","timestamp":1772906546714,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642112683","type":"print"},{"value":"9783642112690","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-11269-0_1","type":"book-chapter","created":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T08:36:15Z","timestamp":1259656575000},"page":"1-16","source":"Crossref","is-referenced-by-count":15,"title":["Balanced Hashing, Color Coding and Approximate Counting"],"prefix":"10.1007","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[]},{"given":"Shai","family":"Gutner","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"1_CR1","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N. Alon","year":"1986","unstructured":"Alon, N., Babai, L., Itai, A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. Journal of Algorithms\u00a07(4), 567\u2013583 (1986)","journal-title":"Journal of Algorithms"},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"Alon, N., Dao, P., Hajirasouliha, I., Hormozdiari, F., Sahinalp, S.C.: Biomolecular network motif counting and discovery by color coding. In: ISMB (Supplement of Bioinformatics), pp. 241\u2013249 (2008)","DOI":"10.1093\/bioinformatics\/btn163"},{"issue":"3","key":"1_CR3","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1002\/rsa.3240030308","volume":"3","author":"N. Alon","year":"1992","unstructured":"Alon, N., Goldreich, O., H\u00e5stad, J., Peralta, R.: Simple construction of almost k-wise independent random variables. Random Struct. Algorithms\u00a03(3), 289\u2013304 (1992)","journal-title":"Random Struct. Algorithms"},{"key":"1_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/978-3-540-73420-8_39","volume-title":"Automata, Languages and Programming","author":"N. Alon","year":"2007","unstructured":"Alon, N., Gutner, S.: Balanced families of perfect hash functions and their applications. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 435\u2013446. Springer, Heidelberg (2007)"},{"issue":"2","key":"1_CR5","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1002\/rsa.3240050203","volume":"5","author":"N. Alon","year":"1994","unstructured":"Alon, N., Roichman, Y.: Random Cayley graphs and expanders. Random Struct. Algorithms\u00a05(2), 271\u2013285 (1994)","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"1_CR6","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1017\/S0963548307008851","volume":"17","author":"N. Alon","year":"2008","unstructured":"Alon, N., Schwartz, O., Shapira, A.: An elementary construction of constant-degree expanders. Combin. Probab. Comput.\u00a017(3), 319\u2013327 (2008)","journal-title":"Combin. Probab. Comput."},{"key":"1_CR7","series-title":"Wiley-Interscience Series in Discrete Mathematics and Optimization","doi-asserted-by":"crossref","DOI":"10.1002\/9780470277331","volume-title":"The probabilistic method","author":"N. Alon","year":"2008","unstructured":"Alon, N., Spencer, J.H.: The probabilistic method. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons Inc., Hoboken (2008)"},{"issue":"4","key":"1_CR8","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N. Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. Journal of the ACM\u00a042(4), 844\u2013856 (1995)","journal-title":"Journal of the ACM"},{"issue":"3","key":"1_CR9","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\u00a017(3), 209\u2013223 (1997)","journal-title":"Algorithmica"},{"key":"1_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/3-540-36136-7_40","volume-title":"Algorithms and Computation","author":"V. Arvind","year":"2002","unstructured":"Arvind, V., Raman, V.: Approximation algorithms for some parameterized counting problems. In: Bose, P., Morin, P. (eds.) ISAAC 2002. LNCS, vol.\u00a02518, pp. 453\u2013464. Springer, Heidelberg (2002)"},{"key":"1_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1007\/978-3-642-04128-0_52","volume-title":"ESA 2009","author":"A. Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Counting paths and packings in halves. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 578\u2013586. Springer, Heidelberg (2009)"},{"key":"1_CR12","volume-title":"An introduction to probability theory and its applications","author":"W. Feller","year":"1968","unstructured":"Feller, W.: An introduction to probability theory and its applications, 3rd edn., vol.\u00a0I. Wiley, New York (1968)","edition":"3"},{"issue":"4","key":"1_CR13","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 Journal on Computing\u00a033(4), 892\u2013922 (2004)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"1_CR14","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M.L. Fredman","year":"1984","unstructured":"Fredman, M.L., Koml\u00f3s, J., Szemer\u00e9di, E.: Storing a sparse table with O(1) worst case access time. Journal of the ACM\u00a031(3), 538\u2013544 (1984)","journal-title":"Journal of the ACM"},{"key":"1_CR15","series-title":"Wiley-Interscience Series in Discrete Mathematics","volume-title":"Combinatorial theory","author":"M. Hall Jr.","year":"1986","unstructured":"Hall Jr., M.: Combinatorial theory, 2nd edn. Wiley-Interscience Series in Discrete Mathematics. John Wiley & Sons Inc., A Wiley-Interscience Publication, New York (1986)","edition":"2"},{"issue":"4","key":"1_CR16","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S. Hoory","year":"2006","unstructured":"Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. Amer. Math. Soc (N.S.)\u00a043(4), 439\u2013561 (2006) (electronic)","journal-title":"Bull. Amer. Math. Soc (N.S.)"},{"key":"1_CR17","doi-asserted-by":"crossref","unstructured":"H\u00fcffner, F., Wernicke, S., Zichner, T.: Algorithm engineering for color-coding to facilitate signaling pathway detection. In: Sankoff, D., Wang, L., Chin, F. (eds.) APBC. Advances in Bioinformatics and Computational Biology, vol.\u00a05, pp. 277\u2013286. Imperial College Press (2007)","DOI":"10.1142\/9781860947995_0030"},{"issue":"2","key":"1_CR18","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci\u00a062(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci"},{"issue":"4","key":"1_CR19","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci.\u00a063(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"1_CR20","series-title":"Texts in Theoretical Computer Science. An EATCS Series","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04650-0","volume-title":"Extremal combinatorics","author":"S. Jukna","year":"2001","unstructured":"Jukna, S.: Extremal combinatorics. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2001); With applications in computer science"},{"key":"1_CR21","doi-asserted-by":"crossref","unstructured":"Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: 36th Annual Symposium on Foundations of Computer Science, pp. 182\u2013191 (1995)","DOI":"10.1109\/SFCS.1995.492475"},{"issue":"5","key":"1_CR22","doi-asserted-by":"publisher","first-page":"775","DOI":"10.1137\/0219054","volume":"19","author":"J.P. Schmidt","year":"1990","unstructured":"Schmidt, J.P., Siegel, A.: The spatial complexity of oblivious k-probe hash functions. SIAM Journal on Computing\u00a019(5), 775\u2013786 (1990)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"1_CR23","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. Journal of Computational Biology\u00a013(2), 133\u2013144 (2006)","journal-title":"Journal of Computational Biology"},{"issue":"4","key":"1_CR24","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1038\/nbt1196","volume":"24","author":"R. Sharan","year":"2006","unstructured":"Sharan, R., Ideker, T.: Modeling cellular machinery through biological network comparison. Nature Biotechnology\u00a024(4), 427\u2013433 (2006)","journal-title":"Nature Biotechnology"},{"key":"1_CR25","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 Bioinformatics\u00a07, 199 (2006)","journal-title":"BMC Bioinformatics"},{"key":"1_CR26","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1145\/1536414.1536477","volume-title":"Proceedings of the 41st Annual ACM Symposium on Theory of Computing","author":"V. Vassilevska","year":"2009","unstructured":"Vassilevska, V., Williams, R.: Finding, minimizing, and counting weighted subgraphs. In: Mitzenmacher, M. (ed.) Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pp. 455\u2013464. ACM, New York (2009)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-11269-0_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T14:45:59Z","timestamp":1739457959000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-11269-0_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642112683","9783642112690"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-11269-0_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}