{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:29:47Z","timestamp":1725488987553},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540744559"},{"type":"electronic","value":"9783540744566"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74456-6_6","type":"book-chapter","created":{"date-parts":[[2007,8,14]],"date-time":"2007-08-14T07:29:48Z","timestamp":1187076588000},"page":"44-55","source":"Crossref","is-referenced-by-count":6,"title":["Expander Properties and the Cover Time of Random Intersection Graphs"],"prefix":"10.1007","author":[{"given":"Sotiris E.","family":"Nikoletseas","sequence":"first","affiliation":[]},{"given":"Christoforos","family":"Raptopoulos","sequence":"additional","affiliation":[]},{"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"unstructured":"Alon, N.: Personal communication (January 2007)","key":"6_CR1"},{"key":"6_CR2","doi-asserted-by":"crossref","DOI":"10.1002\/0471722154","volume-title":"The Probabilistic Method","author":"N. Alon","year":"2000","unstructured":"Alon, N., Spencer, J.: The Probabilistic Method, 2nd edn. Wiley & Sons, Inc., Chichester (2000)","edition":"2"},{"key":"6_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1007\/11523468_55","volume-title":"Automata, Languages and Programming","author":"C. Avin","year":"2005","unstructured":"Avin, C., Ercal, G.: On the Cover Time of Random Geometric Graphs. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 677\u2013689. Springer, Heidelberg (2005)"},{"key":"6_CR4","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":"6_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 Structures and Algorithms\u00a030, 1\u201316 (2007)","journal-title":"Random Structures and Algorithms"},{"issue":"3","key":"6_CR6","doi-asserted-by":"publisher","first-page":"696","DOI":"10.1214\/aoap\/1177005359","volume":"3","author":"P. Diaconis","year":"1993","unstructured":"Diaconis, P., Saloff-Coste, L.: Comparison Theorems for Reversible Markov Chains. The Annals of Applied Probability\u00a03(3), 696\u2013730 (1993)","journal-title":"The Annals of Applied Probability"},{"key":"6_CR7","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1006\/jagm.2000.1149","volume":"39","author":"J. D\u00edaz","year":"2001","unstructured":"D\u00edaz, J., Penrose, M.D., Petit, J., Serna, M.: Approximating Layout Problems on Random Geometric Graphs. Journal of Algorithms\u00a039, 78\u2013116 (2001)","journal-title":"Journal of Algorithms"},{"key":"6_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/3-540-49543-6_23","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"J. D\u00edaz","year":"1998","unstructured":"D\u00edaz, J., Petit, J., Serna, M.: Random Geometric Problems on [0, 1]2. In: Rolim, J.D.P., Serna, M.J., Luby, M. (eds.) RANDOM 1998. LNCS, vol.\u00a01518, pp. 294\u2013306. Springer, Heidelberg (1998)"},{"key":"6_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/3-540-44867-5_8","volume-title":"Experimental and Efficient Algorithms","author":"J. D\u00edaz","year":"2003","unstructured":"D\u00edaz, J., Petit, J., Serna, M.: A Random Graph Model for Optical Networks of Sensors. In: Jansen, K., Margraf, M., Mastrolli, M., Rolim, J.D.P. (eds.) WEA 2003. LNCS, vol.\u00a02647, pp. 186\u2013196. Springer, Heidelberg (2003)"},{"key":"6_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"690","DOI":"10.1007\/11523468_56","volume-title":"Automata, Languages and Programming","author":"C. Efthymiou","year":"2005","unstructured":"Efthymiou, C., Spirakis, P.G.: On the Existence of Hamilton Cycles in Random Intersection Graphs. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 690\u2013701. Springer, Heidelberg (2005)"},{"unstructured":"Fill, J.A., Sheinerman, E.R., Singer-Cohen, K.B.: Random Intersection Graphs when m\u2009=\u2009\u03c9(n): An Equivalence Theorem Relating the Evolution of the G(n, m, p) and G(n, p) models, http:\/\/citeseer.nj.nec.com\/fill98random.html","key":"6_CR11"},{"key":"6_CR12","first-page":"67","volume-title":"Studies in Classification, Data Analysis and Knowledge Organisation","author":"E. Godehardt","year":"2002","unstructured":"Godehardt, E., Jaworski, J.: Two models of Random Intersection Graphs for Classification. In: Opitz, O., Schwaiger, M. (eds.) Studies in Classification, Data Analysis and Knowledge Organisation, pp. 67\u201382. Springer, Heidelberg (2002)"},{"key":"6_CR13","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0890-5401(89)90067-9","volume":"82","author":"M. Jerrum","year":"1989","unstructured":"Jerrum, M., Sinclair, A.: Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains. Information and Computation\u00a082, 93\u2013133 (1989)","journal-title":"Information and Computation"},{"unstructured":"Jerrum, M., Sinclair, A.: The Markov Chain Monte Carlo Method: an Approach to Approximate Counting and Integration. In: Hochbaum, D. (ed.) Approximation Algorithms for NP-hard Problems, PWS, pp. 482\u2013520 (1996)","key":"6_CR14"},{"key":"6_CR15","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1017\/S0963548398003538","volume":"7","author":"J. Jonasson","year":"1998","unstructured":"Jonasson, J.: On the Cover Time of Random Walks on Random Graphs. Combinatorics, Probability and Computing\u00a07, 265\u2013279 (1998)","journal-title":"Combinatorics, Probability and Computing"},{"key":"6_CR16","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1017\/S0963548398003459","volume":"8","author":"M. Karo\u0144ski","year":"1999","unstructured":"Karo\u0144ski, M., Scheinerman, E.R., Singer-Cohen, K.B.: On Random Intersection Graphs: The Subgraph Problem. Combinatorics, Probability and Computing journal\u00a08, 131\u2013159 (1999)","journal-title":"Combinatorics, Probability and Computing journal"},{"key":"6_CR17","doi-asserted-by":"crossref","first-page":"303","DOI":"10.4064\/fm-33-1-303-307","volume":"33","author":"E. Marczewski","year":"1945","unstructured":"Marczewski, E.: Sur deux propri\u00e9t\u00e9s des classes d\u2019 ensembles. Fund. Math.\u00a033, 303\u2013307 (1945)","journal-title":"Fund. Math."},{"key":"6_CR18","series-title":"Lecture Notes in Computer Science","first-page":"247","volume-title":"Automata, Languages, and Programming","author":"S. Nikoletseas","year":"1994","unstructured":"Nikoletseas, S., Palem, K., Spirakis, P.G., Yung, M.: Short Vertex Disjoint Paths and Multiconnectivity in Random Graphs: Reliable Network Computing. In: Shamir, E., Abiteboul, S. (eds.) ICALP 1994. LNCS, vol.\u00a0820, pp. 247\u2013262. Springer, Heidelberg (1994), Also, in the Special Issue on Randomized Computing of the International Journal of Foundations of Computer Science (IJFCS), 11(2), 247-262 (2000)"},{"key":"6_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"1029","DOI":"10.1007\/978-3-540-27836-8_86","volume-title":"Automata, Languages and Programming","author":"S. Nikoletseas","year":"2004","unstructured":"Nikoletseas, S., Raptopoulos, C., Spirakis, P.G.: The Existence and Efficient Construction of Large Independent Sets in General Random Intersection Graphs. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 1029\u20131040. Springer, Heidelberg (2004)"},{"unstructured":"Nikoletseas, S., Raptopoulos, C., Spirakis, P.G.: Expander Properties and the Cover Time of Random Intersection Graphs, DELIS technical report, http:\/\/delis.upb.de\/paper\/DELIS-TR-0491.pdf.","key":"6_CR20"},{"doi-asserted-by":"crossref","unstructured":"Nikoletseas, S., Raptopoulos, C., Spirakis, P.G.: The Second Eigenvalue of Random Walks on Symmetric Random Intersection Graphs. In: Proceedings of the 2nd International Conference on Algebraic Informatics (CAI 2007) (2007)","key":"6_CR21","DOI":"10.1007\/978-3-540-75414-5_15"},{"key":"6_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1007\/3-540-59042-0_93","volume-title":"STACS 1995","author":"S. Nikoletseas","year":"1995","unstructured":"Nikoletseas, S., Spirakis, P.G.: Expander Properties in Random Regular Graphs with Edge Faults. In: Mayr, E.W., Puech, C. (eds.) STACS 1995. LNCS, vol.\u00a0900, pp. 421\u2013432. Springer, Heidelberg (1995)"},{"doi-asserted-by":"crossref","unstructured":"Penrose, M.: Random Geometric Graphs. Oxford Studies in Probability (2003)","key":"6_CR23","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001"},{"key":"6_CR24","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.\u00a03827, pp. 493\u2013504. Springer, Heidelberg (2005)"},{"unstructured":"Sinclair, A.: Algorithms for Random Generation and Counting: a Markov Chain Approach, PhD Thesis, University of Edimburg (1988)","key":"6_CR25"},{"doi-asserted-by":"crossref","unstructured":"Sinclair, A.: In: Birkhauser (ed.) Algorithms for Random Generation and Counting (1992)","key":"6_CR26","DOI":"10.1007\/978-1-4612-0323-0"},{"unstructured":"Singer-Cohen, K.B.: Random Intersection Graphs, PhD thesis, John Hopkins University (1995)","key":"6_CR27"},{"issue":"3","key":"6_CR28","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 Structures & Algorithms\u00a024(3), 249\u2013258 (2004)","journal-title":"Random Structures & Algorithms"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74456-6_6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:29:31Z","timestamp":1619519371000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74456-6_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540744559","9783540744566"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74456-6_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}