{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:09:49Z","timestamp":1725516589531},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540693260"},{"type":"electronic","value":"9783540693550"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-69355-0_10","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"104-118","source":"Crossref","is-referenced-by-count":2,"title":["Recovering the Long-Range Links in Augmented Graphs"],"prefix":"10.1007","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emmanuelle","family":"Lebhar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zvi","family":"Lotker","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Gavoille, C.: Object location using path separators. In: 25th ACM Symp. on Principles of Distributed Computing (PODC), pp. 188\u2013197 (2006)","DOI":"10.1145\/1146381.1146411"},{"key":"10_CR2","unstructured":"Abraham, I., Malkhi, D., Dobzinski, O.: LAND: Stretch (1\u2009+\u2009\u03b5) locality aware networks for DHTs. In: ACM-SIAM Symposium on Discrete Algorithms (SODA) (2004)"},{"issue":"3","key":"10_CR3","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1080\/15427951.2005.10129109","volume":"2","author":"R. Andersen","year":"2006","unstructured":"Andersen, R., Chung, F., Lu, L.: Modeling the small-world phenomenon with local network flow. Internet Mathematics\u00a02(3), 359\u2013385 (2006)","journal-title":"Internet Mathematics"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Clauset, A., Kempe, D., Moore, C.: On the bias of Traceroute sampling, or: power-law degree distributions in regular graphs. In: 37th ACM Symposium on Theory of Computing (STOC) (2005)","DOI":"10.1145\/1060590.1060693"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"Aspnes, J., Diamadi, Z., Shah, G.: Fault-tolerant routing in peer-to-peer systems. In: 21st ACM Symp. on Principles of Distributed Computing (PODC), pp. 223\u2013232 (2002)","DOI":"10.1145\/571825.571862"},{"key":"10_CR6","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"A. Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si, A., Albert, R.: Emergence of scaling in random networks. Science\u00a0286, 509\u2013512 (1999)","journal-title":"Science"},{"key":"10_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/3-540-45414-4_19","volume-title":"Distributed Computing","author":"L. Barri\u00e8re","year":"2001","unstructured":"Barri\u00e8re, L., Fraigniaud, P., Kranakis, E., Krizanc, D.: Efficient routing in networks with long-range contacts. In: Welch, J.L. (ed.) DISC 2001. LNCS, vol.\u00a02180, pp. 270\u2013284. Springer, Heidelberg (2001)"},{"key":"10_CR8","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/978-3-540-44485-5_4","volume":"650","author":"F. Chung","year":"2004","unstructured":"Chung, F., Lu, L.: The small world phenomenon in hybrid power law graphs. Lect. Notes Phys.\u00a0650, 89\u2013104 (2004)","journal-title":"Lect. Notes Phys."},{"issue":"5634","key":"10_CR9","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1126\/science.1081058","volume":"301","author":"P. Dodds","year":"2003","unstructured":"Dodds, P., Muhamad, R., Watts, D.: An experimental study of search in global social networks. Science\u00a0301(5634), 827\u2013829 (2003)","journal-title":"Science"},{"issue":"1","key":"10_CR10","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":"10_CR11","doi-asserted-by":"crossref","unstructured":"Duchon, P., Hanusse, N., Lebhar, E., Schabanel, N.: Towards small world emergence. In: 18th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 225\u2013232 (2006)","DOI":"10.1145\/1148109.1148145"},{"key":"10_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"414","DOI":"10.1007\/11561927_30","volume-title":"Distributed Computing","author":"M. Flammini","year":"2005","unstructured":"Flammini, M., Moscardelli, L., Navarra, A., Perennes, S.: Asymptotically optimal solutions for small world graphs. In: Fraigniaud, P. (ed.) DISC 2005. LNCS, vol.\u00a03724, pp. 414\u2013428. Springer, Heidelberg (2005)"},{"key":"10_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1007\/11561071_70","volume-title":"Algorithms \u2013 ESA 2005","author":"P. Fraigniaud","year":"2005","unstructured":"Fraigniaud, P.: Greedy routing in tree-decomposed graphs: a new perspective on the small-world phenomenon. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 791\u2013802. Springer, Heidelberg (2005)"},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Gavoille, C., Kosowski, A., Lebhar, E., Lotker, Z.: Universal augmentation schemes for network navigability: overcoming the $\\sqrt{n}$ -barrier. In: 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) (2007)","DOI":"10.1145\/1248377.1248379"},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Gavoille, C., Paul, C.: Eclecticism shrinks even small worlds. In: Proceedings of the 23rd ACM Symposium on Principles of Distributed Computing (PODC), pp. 169\u2013178 (2004)","DOI":"10.1145\/1011767.1011793"},{"key":"10_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1007\/11841036_35","volume-title":"Algorithms \u2013 ESA 2006","author":"P. Fraigniaud","year":"2006","unstructured":"Fraigniaud, P., Lebhar, E., Lotker, Z.: A doubling dimension threshold \u0398(loglogn) for augmented graph navigability. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168, pp. 376\u2013386. Springer, Heidelberg (2006)"},{"key":"10_CR17","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.: Bounded geometries, fractals, and low- distortion embeddings. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 534\u2013543 (2003)","DOI":"10.1109\/SFCS.2003.1238226"},{"key":"10_CR18","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0131-8","volume-title":"Lectures on analysis on metric spaces","author":"J. Heinonen","year":"2001","unstructured":"Heinonen, J.: Lectures on analysis on metric spaces. Springer, Heidelberg (2001)"},{"issue":"5","key":"10_CR19","doi-asserted-by":"crossref","first-page":"1148","DOI":"10.1137\/S0097539704446281","volume":"35","author":"S. Har-Peled","year":"2006","unstructured":"Har-Peled, S., Mendel, M.: Fast Construction of Nets in Low Dimensional Metrics, and Their Applications. SICOMP\u00a035(5), 1148\u20131184 (2006)","journal-title":"SICOMP"},{"key":"10_CR20","doi-asserted-by":"crossref","unstructured":"Iamnitchi, A., Ripeanu, M., Foster, I.: Small-world file-sharing communities. In: 23rd Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), pp. 952\u2013963 (2004)","DOI":"10.1109\/INFCOM.2004.1356982"},{"key":"10_CR21","doi-asserted-by":"crossref","unstructured":"Karger, D., Ruhl, M.: Finding nearest neighbors in growth-restricted metrics. In: 34th ACM Symp. on the Theory of Computing (STOC), pp. 63\u201366 (2002)","DOI":"10.1145\/509907.510013"},{"key":"10_CR22","volume-title":"Fundamentals of Statistical Signal Processing: Estimation Theory, ch. 7","author":"S.M. Kay","year":"1993","unstructured":"Kay, S.M.: Fundamentals of Statistical Signal Processing: Estimation Theory, ch. 7. Prentice Hall, Englewood Cliffs (1993)"},{"key":"10_CR23","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.: The small-world phenomenon: an algorithmic perspective. In: 32nd ACM Symp. on Theory of Computing (STOC), pp. 163\u2013170 (2000)","DOI":"10.1145\/335305.335325"},{"key":"10_CR24","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.: Small-World Phenomena and the Dynamics of Information. Advances in Neural Information Processing Systems (NIPS)\u00a014 (2001)","DOI":"10.7551\/mitpress\/1120.003.0060"},{"key":"10_CR25","unstructured":"Kleinberg, J.: Complex networks and decentralized search algorithm. In: Nevanlinna prize presentation at the International Congress of Mathematicians (ICM), Madrid (2006)"},{"key":"10_CR26","doi-asserted-by":"crossref","unstructured":"Krioukov, D., Fall, K., Yang, X.: Compact routing on Internet-like graphs. In: 23rd Conference of the IEEE Communications Society (INFOCOM) (2004)","DOI":"10.1109\/INFCOM.2004.1354495"},{"key":"10_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_44","volume-title":"Algorithms \u2013 ESA 2006","author":"R. Kumar","year":"2006","unstructured":"Kumar, R., Liben-Nowell, D., Tomkins, A.: Navigating Low-Dimensional and Hierarchical Population Networks. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol.\u00a04168. Springer, Heidelberg (2006)"},{"key":"10_CR28","doi-asserted-by":"crossref","unstructured":"Liben-Nowell, D., Novak, J., Kumar, R., Raghavan, P., Tomkins, A.: Geographic routing in social networks. In: Proc. of the Natl. Academy of Sciences of the USA, vol.\u00a0102\/3, pp. 11623\u201311628","DOI":"10.1073\/pnas.0503018102"},{"key":"10_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"894","DOI":"10.1007\/978-3-540-27836-8_75","volume-title":"Automata, Languages and Programming","author":"E. Lebhar","year":"2004","unstructured":"Lebhar, E., Schabanel, N.: Searching for Optimal paths in long-range contact networks. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 894\u2013905. Springer, Heidelberg (2004)"},{"key":"10_CR30","doi-asserted-by":"crossref","unstructured":"Manku, G., Naor, M., Wieder, U.: Know Thy Neighbor\u2019s Neighbor: The Power of Lookahead in Randomized P2P Networks. In: 36th ACM Symp. on Theory of Computing (STOC), pp. 54\u201363 (2004)","DOI":"10.1145\/1007352.1007368"},{"key":"10_CR31","doi-asserted-by":"crossref","unstructured":"Martel, C., Nguyen, V.: Analyzing Kleinberg\u2019s (and other) Small-world Models. In: 23rd ACM Symp. on Principles of Distributed Computing (PODC), pp. 179\u2013188 (2004)","DOI":"10.1145\/1011767.1011794"},{"key":"10_CR32","unstructured":"Martel, C., Nguyen, V.: Analyzing and characterizing small-world graphs. In: 16th ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 311\u2013320 (2005)"},{"key":"10_CR33","unstructured":"Martel, C., Nguyen, V.: Designing networks for low weight, small routing diameter and low congestion. In: 25th Conference of the IEEE Communications Society (INFOCOM) (2006)"},{"key":"10_CR34","doi-asserted-by":"crossref","unstructured":"Milgram, S.: The Small-World Problem. Psychology Today, pp. 60\u201367 (1967)","DOI":"10.1037\/e400002009-005"},{"key":"10_CR35","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1137\/S003614450342480","volume":"45","author":"M. Newman","year":"2003","unstructured":"Newman, M.: The Structure and Function of Complex Networks. SIAM Review\u00a045, 167\u2013256 (2003)","journal-title":"SIAM Review"},{"volume-title":"The Structure and Dynamics of Complex Networks","year":"2006","key":"10_CR36","unstructured":"Newman, M., Barabasi, A., Watts, D. (eds.): The Structure and Dynamics of Complex Networks. Princeton University Press, Princeton (2006)"},{"key":"10_CR37","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511610905","volume-title":"Evolution and Structure of the Internet: A Statistical Physics Approach","author":"R. Pastor-Satorras","year":"2004","unstructured":"Pastor-Satorras, R., Vespignani, A.: Evolution and Structure of the Internet: A Statistical Physics Approach. Cambridge University Press, Cambridge (2004)"},{"key":"10_CR38","doi-asserted-by":"crossref","unstructured":"Slivkins, A.: Distance estimation and object location via rings of neighbors. In: 24th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 41\u201350 (2005)","DOI":"10.1145\/1073814.1073823"},{"key":"10_CR39","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"D. Watts","year":"1998","unstructured":"Watts, D., Strogatz, S.: Collective dynamics of small-world networks. Nature\u00a0393, 440\u2013443 (1998)","journal-title":"Nature"}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-69355-0_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,29]],"date-time":"2024-02-29T06:00:55Z","timestamp":1709186455000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-69355-0_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540693260","9783540693550"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-69355-0_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}