{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:05:45Z","timestamp":1725494745249},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540770039"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-77004-6_15","type":"book-chapter","created":{"date-parts":[[2007,11,14]],"date-time":"2007-11-14T06:40:36Z","timestamp":1195022436000},"page":"187-194","source":"Crossref","is-referenced-by-count":2,"title":["Deterministic Decentralized Search in Random Graphs"],"prefix":"10.1007","author":[{"given":"Esteban","family":"Arcaute","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ning","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ravi","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Liben-Nowell","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammad","family":"Mahdian","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hamid","family":"Nazerzadeh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ying","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"15_CR1","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1080\/10586458.2001.10504428","volume":"10","author":"W. Aiello","year":"2001","unstructured":"Aiello, W., Chung, F., Lu, L.: A random graph model for power law graphs. Experimental Mathematics\u00a010(1), 53\u201366 (2001)","journal-title":"Experimental Mathematics"},{"issue":"15","key":"15_CR2","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"A.-L. Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si, A.-L., Albert, R.: Emergence of scaling in random networks. Science\u00a0286(15), 509\u2013512 (1999)","journal-title":"Science"},{"issue":"3","key":"15_CR3","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1137\/0401033","volume":"1","author":"B. Bollob\u00e1s","year":"1988","unstructured":"Bollob\u00e1s, B., Chung, F.R.K.: The diameter of a cycle plus a random matching. SIAM Journal on Discrete Mathematics\u00a01(3), 328\u2013333 (1988)","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"1","key":"15_CR4","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1080\/15427951.2004.10129081","volume":"1","author":"F. Chung","year":"2003","unstructured":"Chung, F., Lu, L.: The average distance in a random graph with given expected degrees. Internet Mathematics\u00a01(1), 91\u2013114 (2003)","journal-title":"Internet Mathematics"},{"issue":"1","key":"15_CR5","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.tcs.2005.12.008","volume":"355","author":"P. Duchon","year":"2006","unstructured":"Duchon, P., Hanusse, N., Lebhar, E., Schabanel, N.: Could any graph be turned into a small world? Theoretical Computer Science\u00a0355(1), 96\u2013103 (2006)","journal-title":"Theoretical Computer Science"},{"key":"15_CR6","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","volume":"6","author":"P. Erd\u00f6s","year":"1959","unstructured":"Erd\u00f6s, P., R\u00e9nyi, A.: On random graphs I. Publications Mathematics Debrecen\u00a06, 290\u2013297 (1959)","journal-title":"Publications Mathematics Debrecen"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P.: Greedy routing in tree-decomposed graphs. In: Proceedings of the 13th Annual European Symposium on Algorithms, pp. 791\u2013802 (2005)","DOI":"10.1007\/11561071_70"},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.: The small-world phenomenon: An algorithmic perspective. In: Proceedings of the 32nd ACM Symposium on Theory of Computing, pp. 163\u2013170 (2000)","DOI":"10.1145\/335305.335325"},{"key":"15_CR9","first-page":"431","volume":"14","author":"J. Kleinberg","year":"2001","unstructured":"Kleinberg, J.: Small-world phenomena and the dynamics of information. Advances in Neural Information Processing Systems\u00a014, 431\u2013438 (2001)","journal-title":"Advances in Neural Information Processing Systems"},{"key":"15_CR10","doi-asserted-by":"crossref","unstructured":"Kumar, R., Liben-Nowell, D., Tomkins, A.: Navigating low-dimensional and hierarchical population networks. In: Proceedings of the 14th Annual European Symposium on Algorithms, pp. 480\u2013491 (2006)","DOI":"10.1007\/11841036_44"},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Chakrabarti, D., Kleinberg, J., Faloutsos, C.: Realistic, mathematically tractable graph generation and evolution, using Kronecker multiplication. In: Proceedings of the 10th European Conference on Principles and Practice of Knowledge Discovery in Databases, pp. 133\u2013145 (2005)","DOI":"10.1007\/11564126_17"},{"issue":"33","key":"15_CR12","doi-asserted-by":"publisher","first-page":"11623","DOI":"10.1073\/pnas.0503018102","volume":"102","author":"D. Liben-Nowell","year":"2005","unstructured":"Liben-Nowell, D., Novak, J., Kumar, R., Raghavan, P., Tomkins, A.: Geographic routing in social networks. Proceedings of the National Academy of Sciences\u00a0102(33), 11623\u201311628 (2005)","journal-title":"Proceedings of the National Academy of Sciences"},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"Mahdian, M., Xu, Y.: Stochastic Kronecker graphs. In: Proceedings of the 5th Workshop on Algorithms and Models for the Web-Graph (2007)","DOI":"10.1007\/978-3-540-77004-6_14"},{"key":"15_CR14","first-page":"61","volume":"1","author":"S. Milgram","year":"1967","unstructured":"Milgram, S.: The small world problem. Psychology Today\u00a01, 61\u201367 (1967)","journal-title":"Psychology Today"},{"key":"15_CR15","doi-asserted-by":"crossref","unstructured":"Slivkins, A.: Distance estimation and object location via rings of neighbors. In: Proceedings of the 16th ACM Symposium on Principles of Distributed Computing, pp. 41\u201350 (2005)","DOI":"10.1145\/1073814.1073823"},{"key":"15_CR16","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"D.J. Watts","year":"1998","unstructured":"Watts, D.J., Strogatz, S.H.: Collective dynamics of small-world networks. Nature\u00a0393, 440\u2013442 (1998)","journal-title":"Nature"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Models for the Web-Graph"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77004-6_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,14]],"date-time":"2023-05-14T18:30:36Z","timestamp":1684089036000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77004-6_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540770039"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77004-6_15","relation":{},"subject":[]}}