{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T07:33:16Z","timestamp":1725521596130},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540922209"},{"type":"electronic","value":"9783540922216"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"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":[[2008]]},"DOI":"10.1007\/978-3-540-92221-6_15","type":"book-chapter","created":{"date-parts":[[2008,12,3]],"date-time":"2008-12-03T03:25:04Z","timestamp":1228274704000},"page":"217-225","source":"Crossref","is-referenced-by-count":2,"title":["Graph Augmentation via Metric Embedding"],"prefix":"10.1007","author":[{"given":"Emmanuelle","family":"Lebhar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicolas","family":"Schabanel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"15_CR1","doi-asserted-by":"crossref","first-page":"429","DOI":"10.24033\/bsmf.1997","volume":"111","author":"P. Assouad","year":"1983","unstructured":"Assouad, P.: Plongements lipschitzien dans \u211d n . Bull. Soc. Math. France\u00a0111(4), 429\u2013448 (1983)","journal-title":"Bull. Soc. Math. France"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"Abraham, I., Bartal, Y., Neiman, O.: Advances in metric embedding theory. In: Proceeeding of the the 38th annual ACM symposium on Theory of Computing (STOC), pp. 271\u2013286 (2006)","DOI":"10.1145\/1132516.1132557"},{"key":"15_CR3","unstructured":"Abraham, I., Bartal, Y., Neiman, O.: Embedding Metric Spaces in their Intrinsic Dimension. In: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms (SODA), pp. 363\u2013372 (2008)"},{"key":"15_CR4","doi-asserted-by":"crossref","unstructured":"Abraham, I., Gavoille, C.: Object location using path separators. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 188\u2013197 (2006)","DOI":"10.1145\/1146381.1146411"},{"key":"15_CR5","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/BF02776078","volume":"52","author":"J. Bourgain","year":"1985","unstructured":"Bourgain, J.: On Lipschitz embedding of finite metric spaces in Hilbert space. Israel Journal of Mathematics\u00a052, 46\u201352 (1985)","journal-title":"Israel Journal of Mathematics"},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"Dabek, F., Cox, R., Kaashoek, F., Morris, R.: Vivaldi: A decentralized network coordinate system. In: ACM SIGCOMM (2004)","DOI":"10.1145\/1015467.1015471"},{"issue":"1","key":"15_CR7","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_CR8","doi-asserted-by":"crossref","unstructured":"Duchon, P., Hanusse, N., Lebhar, E., Schabanel, N.: Towards small world emergence. In: 18th Annual ACM Symp. on Parallel Algorithms and Architectures (SPAA), pp. 225\u2013232 (2006)","DOI":"10.1145\/1148109.1148145"},{"key":"15_CR9","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1126\/science.1081058","volume":"301","author":"P.S. Dodds","year":"2003","unstructured":"Dodds, P.S., Muhamad, R., Watts, D.J.: An experimental study of search in global social networks. Science\u00a0301, 827\u2013829 (2003)","journal-title":"Science"},{"key":"15_CR10","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":"15_CR11","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Gavoille, C.: Polylogarithmic network navigability using compact metrics with small stretch. In: 20th Annual ACM Symp. on Parallel Algorithms and Architectures (SPAA), pp. 62\u201369 (2008)","DOI":"10.1145\/1378533.1378542"},{"key":"15_CR12","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: Proceedings of the 19th Annual ACM Symposium on Parallel Algorithms and Architecture (SPAA), pp. 1\u20137 (2007)","DOI":"10.1145\/1248377.1248379"},{"key":"15_CR13","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":"15_CR14","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: 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":"15_CR15","unstructured":"Indyk, P.: Algorithmic aspects of geometric embeddings. In: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, FOCS (2001)"},{"key":"15_CR16","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1090\/conm\/026\/737400","volume":"26","author":"W.B. Johnson","year":"1984","unstructured":"Johnson, W.B., Lindenstrauss, J.: Extensions of Lipschitz maps into a Hilbert space. Contemporary mathematics\u00a026, 189\u2013206 (1984)","journal-title":"Contemporary mathematics"},{"key":"15_CR17","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.: The Small-World Phenomenon: An Algorithmic Perspective. In: 32nd ACM Symp. on Theo. of Comp. (STOC), pp. 163\u2013170 (2000)","DOI":"10.1145\/335305.335325"},{"key":"15_CR18","unstructured":"Kleinberg, J.: Small-World Phenomena and the Dynamics of Information. Advances in Neural Information Processing Systems (NIPS)\u00a014 (2001)"},{"key":"15_CR19","unstructured":"Kleinberg, J.: Complex networks and decentralized search algorithm. In: Intl. Congress of Math, ICM (2006)"},{"key":"15_CR20","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0039-7","volume-title":"Lectures on Discrete Geometry","author":"J. Matousek","year":"2002","unstructured":"Matousek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol.\u00a0212. Springer, Heidelberg (2002)"},{"key":"15_CR21","doi-asserted-by":"crossref","unstructured":"Milgram, S.: The Small-World Problem. Psychology Today, 60\u201367 (1967)","DOI":"10.1037\/e400002009-005"},{"key":"15_CR22","doi-asserted-by":"crossref","unstructured":"Slivkins, A.: Distance estimation and object location via rings of neighbors. In: 24th Annual ACM Symp. on Princ. of Distr. Comp. (PODC), pp. 41\u201350 (2005)","DOI":"10.1145\/1073814.1073823"},{"key":"15_CR23","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 \u2019small-world\u2019 networks. Nature\u00a0393, 440\u2013442 (1998)","journal-title":"Nature"}],"container-title":["Lecture Notes in Computer Science","Principles of Distributed Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-92221-6_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T19:11:20Z","timestamp":1557947480000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-92221-6_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540922209","9783540922216"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-92221-6_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}