{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T17:18:54Z","timestamp":1743095934972,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319240237"},{"type":"electronic","value":"9783319240244"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-24024-4_21","type":"book-chapter","created":{"date-parts":[[2015,9,4]],"date-time":"2015-09-04T08:00:10Z","timestamp":1441353610000},"page":"370-383","source":"Crossref","is-referenced-by-count":4,"title":["On Some Combinatorial Properties of Random Intersection Graphs"],"prefix":"10.1007","author":[{"given":"Sotiris E.","family":"Nikoletseas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christoforos L.","family":"Raptopoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,22]]},"reference":[{"unstructured":"Aldous, D., Fill, J.A.: Reversible Markov Chains and Random Walks on Graphs. Unfinished monograph, recompiled (2014). Accessed on \n                      http:\/\/www.stat.berkeley.edu\/~aldous\/RWG\/book.html","key":"21_CR1"},{"key":"21_CR2","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1137\/050647153","volume":"23","author":"M Behrisch","year":"2008","unstructured":"Behrisch, M., Taraz, A., Ueckerdt, M.: Coloring random intersection graphs and complex networks. SIAM J. Discrete Math. 23, 288\u2013299 (2008)","journal-title":"SIAM J. Discrete Math."},{"issue":"1\u20132","key":"21_CR3","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/s10623-010-9481-x","volume":"64","author":"S Blackburn","year":"2012","unstructured":"Blackburn, S., Stinson, D., Upadhyay, J.: On the complexity of the herding attack and some related attacks on hash functions. Des. Codes Crypt. 64(1\u20132), 171\u2013193 (2012)","journal-title":"Des. Codes Crypt."},{"key":"21_CR4","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1002\/net.20256","volume":"53","author":"M Bloznelis","year":"2009","unstructured":"Bloznelis, M., Jaworski, J., Rybarczyk, K.: Component evolution in a secure wireless sensor network. Networks 53, 19\u201326 (2009)","journal-title":"Networks"},{"key":"21_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/rsa.20151","volume":"30","author":"C Cooper","year":"2007","unstructured":"Cooper, C., Frieze, A.: The cover time of sparse random graphs. Random Struct. Algorithms 30, 1\u201316 (2007)","journal-title":"Random Struct. Algorithms"},{"key":"21_CR6","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1017\/S0269964809990064","volume":"23","author":"M Deijfen","year":"2009","unstructured":"Deijfen, M., Kets, W.: Random intersection graphs with tunable degree distribution and clustering. Probab. Eng. Inform. Sci. 23, 661\u2013674 (2009)","journal-title":"Probab. Eng. Inform. Sci."},{"unstructured":"Chan, H., Perrig, A., Song, D.: Random key predistribution schemes for sensor networks. In: Proceedings of the IEEE Symposium on Security and Privacy (2003)","key":"21_CR7"},{"issue":"40\u201342","key":"21_CR8","doi-asserted-by":"publisher","first-page":"3714","DOI":"10.1016\/j.tcs.2010.06.022","volume":"411","author":"C Efthymiou","year":"2010","unstructured":"Efthymiou, C., Spirakis, P.G.: Sharp thresholds for Hamiltonicity in random intersection graphs. Theor. Comput. Sci. 411(40\u201342), 3714\u20133730 (2010)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"21_CR9","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1002\/(SICI)1098-2418(200003)16:2<156::AID-RSA3>3.0.CO;2-H","volume":"16","author":"JA Fill","year":"2000","unstructured":"Fill, J.A., Sheinerman, E.R., Singer-Cohen, K.B.: Random intersection graphs when \n                      \n                        \n                      \n                      $$m = \\omega (n)$$\n                    : an equivalence theorem relating the evolution of the \n                      \n                        \n                      \n                      $$G(n, m, p)$$\n                     and \n                      \n                        \n                      \n                      $$G(n, p)$$\n                     models. Random Struct. Algorithms 16(2), 156\u2013176 (2000)","journal-title":"Random Struct. Algorithms"},{"key":"21_CR10","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/0012-365X(90)90149-C","volume":"81","author":"A Frieze","year":"1990","unstructured":"Frieze, A.: On the Independence Number of Random Graphs. Disc. Math. 81, 171\u2013175 (1990)","journal-title":"Disc. Math."},{"key":"21_CR11","series-title":"Studies in Classification, Data Analysis, and Knowledge Organization","first-page":"67","volume-title":"Exploratory Data Analysis in Empirical Research","author":"E Godehardt","year":"2002","unstructured":"Godehardt, E., Jaworski, J.: Two models of random intersection graphs for classification. In: Opitz, O., Schwaiger, M. (eds.) Exploratory Data Analysis in Empirical Research. Studies in Classification, Data Analysis, and Knowledge Organization, pp. 67\u201382. Springer, Heidelberg (2002)"},{"key":"21_CR12","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1017\/S0963548398003459","volume":"8","author":"M Karo\u0144ski","year":"1999","unstructured":"Karo\u0144ski, M., Sheinerman, E.R., Singer-Cohen, K.B.: On random intersection graphs: the subgraph problem. Comb. Probab. Comput. j. 8, 131\u2013159 (1999)","journal-title":"Comb. Probab. Comput. j."},{"issue":"1","key":"21_CR13","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/BF01375472","volume":"11","author":"T \u0141uczak","year":"2005","unstructured":"\u0141uczak, T.: The chromatic number of random graphs. Combinatorica 11(1), 45\u201354 (2005)","journal-title":"Combinatorica"},{"key":"21_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"600","DOI":"10.1007\/978-3-642-03816-7_51","volume-title":"Mathematical Foundations of Computer Science 2009","author":"S Nikoletseas","year":"2009","unstructured":"Nikoletseas, S., Raptopoulos, C., Spirakis, P.G.: Colouring non-sparse random intersection graphs. In: Kr\u00e1lovi\u010d, R., Niwi\u0144ski, D. (eds.) MFCS 2009. LNCS, vol. 5734, pp. 600\u2013611. Springer, Heidelberg (2009)"},{"issue":"50","key":"21_CR15","doi-asserted-by":"publisher","first-page":"5261","DOI":"10.1016\/j.tcs.2009.08.028","volume":"410","author":"S Nikoletseas","year":"2009","unstructured":"Nikoletseas, S., Raptopoulos, C., Spirakis, P.G.: Expander properties and the cover time of random intersection graphs. Theor. Comput. Sci. 410(50), 5261\u20135272 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"21_CR16","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/j.tcs.2008.06.047","volume":"406","author":"S Nikoletseas","year":"2008","unstructured":"Nikoletseas, S., Raptopoulos, C., Spirakis, P.G.: Large independent sets in general random intersection graphs. Theor. Comput. Sci. 406, 215\u2013224 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"21_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"728","DOI":"10.1007\/978-3-642-32589-2_63","volume-title":"Mathematical Foundations of Computer Science 2012","author":"S Nikoletseas","year":"2012","unstructured":"Nikoletseas, S., Raptopoulos, C., Spirakis, P.G.: Maximum cliques in graphs with small intersection number and random intersection graphs. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 728\u2013739. Springer, Heidelberg (2012)"},{"issue":"48","key":"21_CR18","doi-asserted-by":"publisher","first-page":"6750","DOI":"10.1016\/j.tcs.2011.09.003","volume":"412","author":"S Nikoletseas","year":"2011","unstructured":"Nikoletseas, S., Raptopoulos, C., Spirakis, P.G.: On the independence number and hamiltonicity of uniform random intersection graphs. Theor. Comput. Sci. 412(48), 6750\u20136760 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"21_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04016-0","volume-title":"Graph Colouring and the Probabilistic Method","author":"M Molloy","year":"2002","unstructured":"Molloy, M., Reed, B.: Graph Colouring and the Probabilistic Method. Springer, Heidelberg (2002)"},{"key":"21_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/11602613_50","volume-title":"Algorithms and Computation","author":"C Raptopoulos","year":"2005","unstructured":"Raptopoulos, C., Spirakis, P.G.: Simple and efficient greedy algorithms for hamilton cycles in random intersection graphs. In: Deng, X., Du, D.-Z. (eds.) ISAAC 2005. LNCS, vol. 3827, pp. 493\u2013504. Springer, Heidelberg (2005)"},{"issue":"1\u20132","key":"21_CR21","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1002\/rsa.20356","volume":"38","author":"K Rybarczyk","year":"2011","unstructured":"Rybarczyk, K.: Equivalence of a random intersection graph and \n                      \n                        \n                      \n                      $$G(n, p)$$\n                    . Random Struct. Algorithms 38(1\u20132), 205\u2013234 (2011)","journal-title":"Random Struct. Algorithms"},{"doi-asserted-by":"publisher","unstructured":"Shang, Y.: On the isolated vertices and connectivity in random intersection graphs. Int. J. Comb. 2011. Article ID 872703 (2011). doi:\n                      10.1155\/2011\/872703","key":"21_CR22","DOI":"10.1155\/2011\/872703"},{"unstructured":"Singer-Cohen, K.B.: Random Intersection Graphs. Ph.D. thesis, John Hopkins University (1995)","key":"21_CR23"},{"issue":"3","key":"21_CR24","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1002\/rsa.20005","volume":"24","author":"D Stark","year":"2004","unstructured":"Stark, D.: The vertex degree distribution of random intersection graphs. Random Struct. Algorithms 24(3), 249\u2013258 (2004)","journal-title":"Random Struct. Algorithms"},{"issue":"5","key":"21_CR25","doi-asserted-by":"publisher","first-page":"2983","DOI":"10.1109\/TIT.2011.2181331","volume":"58","author":"O Ya\u011fan","year":"2012","unstructured":"Ya\u011fan, O., Makowski, A.M.: Zero-one laws for connectivity in random key graphs. IEEE Trans. Inf. Theor. 58(5), 2983\u20132999 (2012)","journal-title":"IEEE Trans. Inf. Theor."},{"unstructured":"Zhao, J., Ya\u011fan, O., Gligor, V.: On \n                      \n                        \n                      \n                      $$k$$\n                    -connectivity and minimum vertex degree in random \n                      \n                        \n                      \n                      $$s$$\n                    -intersection graphs. Arxiv e-prints (2014). Accessed on \n                      http:\/\/arxiv.org\/pdf\/1409.6021v3.pdf","key":"21_CR26"},{"doi-asserted-by":"crossref","unstructured":"Zhao, J., Ya\u011fan, O., Gligor, V.: On the strengths of connectivity and robustness in general random intersection graphs. In: Proceedings of the IEEE Conference on Decision and Control (CDC), December 2014","key":"21_CR27","DOI":"10.1109\/CDC.2014.7039959"}],"container-title":["Lecture Notes in Computer Science","Algorithms, Probability, Networks, and Games"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-24024-4_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T17:42:49Z","timestamp":1559238169000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-24024-4_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319240237","9783319240244"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-24024-4_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}