{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T02:39:43Z","timestamp":1768617583367,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642137303","type":"print"},{"value":"9783642137310","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13731-0_39","type":"book-chapter","created":{"date-parts":[[2010,6,10]],"date-time":"2010-06-10T07:00:50Z","timestamp":1276153250000},"page":"420-431","source":"Crossref","is-referenced-by-count":55,"title":["Minimizing the Diameter of a Network Using Shortcut Edges"],"prefix":"10.1007","author":[{"given":"Erik D.","family":"Demaine","sequence":"first","affiliation":[]},{"given":"Morteza","family":"Zadimoghaddam","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"39_CR1","doi-asserted-by":"crossref","unstructured":"Albers, S., Eilts, S., Even-Dar, E., Mansour, Y., Roditty, L.: On Nash equilibria for a network creation game. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, pp. 89\u201398 (2006)","DOI":"10.1145\/1109557.1109568"},{"issue":"1","key":"39_CR2","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1109\/2.976921","volume":"35","author":"L. Benini","year":"2002","unstructured":"Benini, L., De Micheli, G.: Networks on chips: A new SoC paradigm. Computer\u00a035(1), 70\u201378 (2002)","journal-title":"Computer"},{"key":"39_CR3","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for the facility location and k-median problems. In: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, pp. 378\u2013388 (1999)","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"39_CR4","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Hajiaghayi, M.T., Mahini, H., Zadimoghaddam, M.: The price of anarchy in cooperative network creation games. SIGecom Exchanges\u00a08(2) (December 2009)","DOI":"10.1145\/1980522.1980524"},{"key":"#cr-split#-39_CR5.1","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Hajiaghayi, M.T., Mahini, H., Zadimoghaddam, M.: The price of anarchy in network creation games. In: Proceedings of the 26th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp. 292???298 (2007);","DOI":"10.1145\/1281100.1281142"},{"key":"#cr-split#-39_CR5.2","unstructured":"To appear in ACM Transactions on Algorithms"},{"key":"39_CR6","doi-asserted-by":"crossref","unstructured":"Fabrikant, A., Luthra, A., Maneva, E., Papadimitriou, C.H., Shenker, S.: On a network creation game. In: Proceedings of the 22nd Annual Symposium on Principles of Distributed Computing, Boston, MA, pp. 347\u2013351 (2003)","DOI":"10.1145\/872035.872088"},{"issue":"4","key":"39_CR7","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U. Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. Journal of the ACM\u00a045(4), 634\u2013652 (1998)","journal-title":"Journal of the ACM"},{"key":"39_CR8","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":"39_CR9","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":"39_CR10","doi-asserted-by":"crossref","unstructured":"Laoutaris, N., Poplawski, L., Rajaraman, R., Sundaram, R., Teng, S.-H.: Bounded budget connection (BBC) games or how to make friends and influence people, on a budget. In: Proceedings of the 27th ACM Symposium on Principles of Distributed Computing, pp. 165\u2013174 (2008)","DOI":"10.1145\/1400751.1400774"},{"key":"39_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1007\/978-3-642-03685-9_21","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"A. Meyerson","year":"2009","unstructured":"Meyerson, A., Tagiku, B.: Minimizing average shortest path distances via shortcut edge addition. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. LNCS, vol.\u00a05687, pp. 272\u2013285. Springer, Heidelberg (2009)"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory - SWAT 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13731-0_39.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T21:42:25Z","timestamp":1606167745000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13731-0_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642137303","9783642137310"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13731-0_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}