{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T15:50:14Z","timestamp":1787068214273,"version":"build-2736575974"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T00:00:00Z","timestamp":1559260800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T00:00:00Z","timestamp":1559260800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001736","name":"German-Israeli Foundation for Scientific Research and Development","doi-asserted-by":"crossref","award":["I-1245-407.6\/2014"],"award-info":[{"award-number":["I-1245-407.6\/2014"]}],"id":[{"id":"10.13039\/501100001736","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2020,6]]},"DOI":"10.1007\/s00446-019-00351-5","type":"journal-article","created":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T06:02:41Z","timestamp":1559282561000},"page":"311-325","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Demand-aware network designs of bounded degree"],"prefix":"10.1007","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6647-8002","authenticated-orcid":false,"given":"Chen","family":"Avin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kaushik","family":"Mondal","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefan","family":"Schmid","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,5,31]]},"reference":[{"issue":"4","key":"351_CR1","doi-asserted-by":"publisher","first-page":"1167","DOI":"10.1137\/S0097539796303421","volume":"28","author":"D Aingworth","year":"1999","unstructured":"Aingworth, D., Chekuri, C., Indyk, P., Motwani, R.: Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput. 28(4), 1167\u20131181 (1999)","journal-title":"SIAM J. Comput."},{"key":"351_CR2","doi-asserted-by":"crossref","unstructured":"Avin, C., Borokhovich, M., Haeupler, B., Lotker, Z.: Self-adjusting grid networks to minimize expected path length. Theor. Comput. Sci. 584, 91\u2013102 (2015). Special Issue on Structural Information and Communication Complexity","DOI":"10.1016\/j.tcs.2014.11.036"},{"key":"351_CR3","doi-asserted-by":"crossref","unstructured":"Avin, C., Borokhovich, M., Schmid, S.: OBST: a self-adjusting peer-to-peer overlay based on multiple BSTs. In: Proceedings of the 13th IEEE International Conference on Peer-to-Peer Computing (P2P) (2013)","DOI":"10.1109\/P2P.2013.6688721"},{"key":"351_CR4","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1016\/j.ipl.2017.12.008","volume":"133","author":"C Avin","year":"2018","unstructured":"Avin, C., Hercules, A., Loukas, A., Schmid, S.: rDAN: toward robust demand-aware network designs. Inf. Process. Lett. (IPL) 133, 5\u20139 (2018)","journal-title":"Inf. Process. Lett. (IPL)"},{"key":"351_CR5","unstructured":"Avin, C., Mondal, K., Schmid, S.: Demand-aware network designs of bounded degree. In: Proceedings of the International Symposium on Distributed Computing (DISC) (2017)"},{"key":"351_CR6","doi-asserted-by":"crossref","unstructured":"Avin, C., Mondal, K., Schmid, S.: Demand-aware network design with minimal congestion and route lengths. In: Proceedings of the IEEINFOCOM (2019)","DOI":"10.1109\/INFOCOM.2019.8737431"},{"key":"351_CR7","doi-asserted-by":"crossref","unstructured":"Avin, C., Schmid, S.: Toward demand-aware networking: a theory for self-adjusting networks. In: ACM SIGCOMM Computer Communication Review (CCR) (2018)","DOI":"10.1145\/3310165.3310170"},{"issue":"1","key":"351_CR8","doi-asserted-by":"publisher","first-page":"5:1","DOI":"10.1145\/1868237.1868242","volume":"7","author":"S Baswana","year":"2010","unstructured":"Baswana, S., Kavitha, T., Mehlhorn, K., Pettie, S.: Additive spanners and (alpha, beta)-spanners. ACM Trans. Algorithms 7(1), 5:1\u20135:26 (2010)","journal-title":"ACM Trans. Algorithms"},{"key":"351_CR9","doi-asserted-by":"crossref","unstructured":"Chan, H., Dinitz, M., Gupta, A.: Spanners with slack. In: Proceedings of the European Symposium on Algorithms (ESA) (2006)","DOI":"10.1007\/11841036_20"},{"issue":"1","key":"351_CR10","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/s00454-008-9115-5","volume":"41","author":"T-HH Chan","year":"2009","unstructured":"Chan, T.-H.H., Gupta, A.: Small hop-diameter sparse spanners for doubling metrics. Discrete Comput. Geom. 41(1), 28\u201344 (2009)","journal-title":"Discrete Comput. Geom."},{"key":"351_CR11","first-page":"55:1","volume":"4","author":"T-HH Chan","year":"2016","unstructured":"Chan, T.-H.H., Gupta, A., Maggs, B.M., Zhou, S.: On hierarchical routing in doubling metrics. ACM Trans. Algorithms 4, 55:1\u201355:22 (2016)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"351_CR12","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1007\/s00453-008-9191-1","volume":"56","author":"M Charikar","year":"2010","unstructured":"Charikar, M., Hajiaghayi, M.T., Karloff, H.J., Rao, S.: $$\\text{ l }_{\\text{2 }}{}^{\\text{2 }}$$ spreading metrics for vertex ordering problems. Algorithmica 56(4), 577\u2013604 (2010)","journal-title":"Algorithmica"},{"key":"351_CR13","doi-asserted-by":"crossref","unstructured":"Chen, C., Vitenberg, R., Jacobsen, H.A.: Scaling construction of low fan-out overlays for topic-based publish\/subscribe systems. In: 2011 31st International Conference on Distributed Computing Systems, pp. 225\u2013236 (2011)","DOI":"10.1109\/ICDCS.2011.68"},{"issue":"1","key":"351_CR14","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1006\/jctb.1994.1056","volume":"62","author":"FRK Chung","year":"1994","unstructured":"Chung, F.R.K., Mumford, D.: Chordal completions of planar graphs. J. Comb. Theory Ser. B 62(1), 96\u2013106 (1994)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"351_CR15","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1137\/050630696","volume":"20","author":"D Coppersmith","year":"2006","unstructured":"Coppersmith, D., Elkin, M.: Sparse sourcewise and pairwise distance preservers. SIAM J. Discrete Math. 20(2), 463\u2013501 (2006)","journal-title":"SIAM J. Discrete Math."},{"key":"351_CR16","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge (2009)","edition":"3"},{"key":"351_CR17","volume-title":"Elements of Information Theory","author":"TM Cover","year":"2012","unstructured":"Cover, T.M., Thomas, J.A.: Elements of Information Theory. Wiley, New York (2012)"},{"issue":"1","key":"351_CR18","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.ins.2010.08.041","volume":"181","author":"M Dehmer","year":"2011","unstructured":"Dehmer, M., Mowshowitz, A.: A history of graph entropy measures. Inf. Sci. 181(1), 57\u201378 (2011)","journal-title":"Inf. Sci."},{"key":"351_CR19","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Harmon, D., Iacono, J., Kane, D., Patra\u015fcu, M.: The geometry of binary search trees. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 496\u2013505. SIAM, Philadelphia (2009)","DOI":"10.1137\/1.9781611973068.55"},{"issue":"1","key":"351_CR20","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1137\/S0097539705447347","volume":"37","author":"ED Demaine","year":"2007","unstructured":"Demaine, E.D., Harmon, D., Iacono, J., Patrascu, M.: Dynamic optimality\u2014almost. SIAM J. Comput. 37(1), 240\u2013251 (2007)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"351_CR21","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1137\/S0097539701393384","volume":"33","author":"M Elkin","year":"2004","unstructured":"Elkin, M., Peleg, D.: $$(1 + \\epsilon,\\beta )$$-spanner constructions for general graphs. SIAM J. Comput. 33(3), 608\u2013631 (2004)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"351_CR22","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.ipl.2006.07.009","volume":"101","author":"U Feige","year":"2007","unstructured":"Feige, U., Lee, J.R.: An improved approximation ratio for the minimum linear arrangement problem. Inf. Process. Lett. 101(1), 26\u201329 (2007)","journal-title":"Inf. Process. Lett."},{"key":"351_CR23","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Lebhar, E., Lotker, Z.: A doubling dimension threshold $$\\theta $$ (log log n) for augmented graph navigability. In: ESA, pp. 376\u2013386. Springer, Berlin (2006)","DOI":"10.1007\/11841036_35"},{"key":"351_CR24","doi-asserted-by":"crossref","unstructured":"Ghobadi, M., et\u00a0al.: Projector: Agile reconfigurable data center interconnect. In: Proceedings of the ACM SIGCOMM, pp. 216\u2013229 (2016)","DOI":"10.1145\/2934872.2934911"},{"key":"351_CR25","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings. In: Proceedings of the IEEE FOCS, pp. 534\u2013543 (2003)"},{"issue":"5","key":"351_CR26","doi-asserted-by":"publisher","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. SIAM J. Comput. 35(5), 1148\u20131184 (2006)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"351_CR27","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1137\/0112012","volume":"12","author":"LH Harper","year":"1964","unstructured":"Harper, L.H.: Optimal assignments of numbers to vertices. J. Soc. Ind. Appl. Math. 12(1), 131\u2013135 (1964)","journal-title":"J. Soc. Ind. Appl. Math."},{"issue":"1","key":"351_CR28","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1006\/jagm.2002.1217","volume":"43","author":"V Heun","year":"2002","unstructured":"Heun, V., Mayr, E.W.: Embedding graphs with bounded treewidth into their optimal hypercubes. J. Algorithms 43(1), 17\u201350 (2002)","journal-title":"J. Algorithms"},{"key":"351_CR29","doi-asserted-by":"crossref","unstructured":"Huq, S., Ghosh, S.: Locally self-adjusting skip graphs. In: 37th IEEE International Conference on Distributed Computing Systems, ICDCS 2017, Atlanta, GA, USA, June 5\u20138, pp. 805\u2013815 (2017)","DOI":"10.1109\/ICDCS.2017.249"},{"key":"351_CR30","doi-asserted-by":"crossref","unstructured":"Jia, S., Jin, X., Ghasemiesfeh, G., Ding, J., Gao, J.: Competitive analysis for online scheduling in software-defined optical WAN. In: Proceedings of the IEEE INFOCOM (2017)","DOI":"10.1109\/INFOCOM.2017.8056969"},{"issue":"4","key":"351_CR31","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1002\/net.3230080402","volume":"8","author":"DS Johnson","year":"1978","unstructured":"Johnson, D.S., Lenstra, J.K., Kan, A.H.G.R.: The complexity of the network design problem. Networks 8(4), 279\u2013285 (1978)","journal-title":"Networks"},{"key":"351_CR32","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/BF00264563","volume":"5","author":"K Mehlhorn","year":"1975","unstructured":"Mehlhorn, K.: Nearly optimal binary search trees. Acta Inf. 5, 287\u2013295 (1975)","journal-title":"Acta Inf."},{"key":"351_CR33","doi-asserted-by":"crossref","unstructured":"Meyerson, A., Tagiku, B.: Minimizing average shortest path distances via shortcut edge addition. In: Proceedings of the APPROX\/RANDOM, pp. 272\u2013285. Berlin (2009)","DOI":"10.1007\/978-3-642-03685-9_21"},{"issue":"5","key":"351_CR34","doi-asserted-by":"publisher","first-page":"1331","DOI":"10.1109\/TNET.2011.2144999","volume":"19","author":"M Onus","year":"2011","unstructured":"Onus, M., Richa, A.W.: Minimum maximum-degree publish-subscribe overlay network design. IEEE\/ACM Trans. Netw. 19(5), 1331\u20131343 (2011)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"351_CR35","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/j.comnet.2015.10.023","volume":"94","author":"M Onus","year":"2016","unstructured":"Onus, M., Richa, A.W.: Parameterized maximum and average degree approximation in topic-based publish-subscribe overlay network design. Comput. Netw. 94, 307\u2013317 (2016)","journal-title":"Comput. Netw."},{"issue":"1","key":"351_CR36","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D Peleg","year":"1989","unstructured":"Peleg, D., Sch\u00e4ffer, A.A.: Graph spanners. J. Graph Theory 13(1), 99\u2013116 (1989)","journal-title":"J. Graph Theory"},{"issue":"4","key":"351_CR37","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1137\/0218050","volume":"18","author":"D Peleg","year":"1989","unstructured":"Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. SIAM J. Comput. 18(4), 740\u2013747 (1989)","journal-title":"SIAM J. Comput."},{"key":"351_CR38","doi-asserted-by":"crossref","unstructured":"Peres, B., Souza, O., Goussevskaia, O., Schmid, S., Avin, C.: Distributed self-adjusting tree networks. In: Proceedings of the IEE INFOCOM (2019)","DOI":"10.1109\/INFOCOM.2019.8737417"},{"issue":"1","key":"351_CR39","doi-asserted-by":"publisher","first-page":"7:1","DOI":"10.1145\/1644015.1644022","volume":"6","author":"S Pettie","year":"2009","unstructured":"Pettie, S.: Low distortion spanners. ACM Trans. Algorithms 6(1), 7:1\u20137:22 (2009)","journal-title":"ACM Trans. Algorithms"},{"issue":"5","key":"351_CR40","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1145\/2829988.2787472","volume":"45","author":"A Roy","year":"2015","unstructured":"Roy, A., Zeng, H., Bagga, J., Porter, G., Snoeren, A.C.: Inside the social network\u2019s (datacenter) network. Comput. Commun. Rev. 45(5), 123\u2013137 (2015)","journal-title":"Comput. Commun. Rev."},{"issue":"3","key":"351_CR41","doi-asserted-by":"publisher","first-page":"1421","DOI":"10.1109\/TNET.2015.2410313","volume":"24","author":"S Schmid","year":"2016","unstructured":"Schmid, S., Avin, C., Scheideler, C., Borokhovich, M., Haeupler, B., Lotker, Z.: Splaynet: towards locally self-adjusting networks. IEEE\/ACM Trans. Netw. 24(3), 1421\u20131433 (2016)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"351_CR42","doi-asserted-by":"crossref","unstructured":"Singla, A.: Fat-free topologies. In: Proceedings of the 15th ACM Workshop on Hot Topics in Networks (HotNets), pp. 64\u201370 (2016)","DOI":"10.1145\/3005745.3005747"},{"key":"351_CR43","unstructured":"Singla, A., Godfrey, P.B., Kolla, A.: High throughput data center topology design. In: NSDI, pp. 29\u201341 (2014)"},{"issue":"3","key":"351_CR44","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1145\/3828.3835","volume":"32","author":"DD Sleator","year":"1985","unstructured":"Sleator, D.D., Tarjan, R.E.: Self-adjusting binary search trees. J. ACM 32(3), 652\u2013686 (1985)","journal-title":"J. ACM"},{"key":"351_CR45","doi-asserted-by":"crossref","unstructured":"Spielman, D.A., Teng, S.-H.: Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In: Proceedings of the ACM STOC, pp. 81\u201390 (2004)","DOI":"10.1145\/1007352.1007372"},{"key":"351_CR46","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Spanners and emulators with sublinear distance errors. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA \u201906, pp. 802\u2013809. Society for Industrial and Applied Mathematics, Philadelphia (2006)","DOI":"10.1145\/1109557.1109645"},{"key":"351_CR47","doi-asserted-by":"crossref","unstructured":"Wang, C.C., Derryberry, J., Sleator, D.D.: O(log log n)-competitive dynamic binary search trees. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA \u201906, pp. 374\u2013383. Society for Industrial and Applied Mathematics, Philadelphia (2006)","DOI":"10.1145\/1109557.1109600"},{"issue":"3","key":"351_CR48","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1016\/0743-7315(85)90026-7","volume":"2","author":"AY Wu","year":"1985","unstructured":"Wu, A.Y.: Embedding of tree networks into hypercubes. J. Parallel Distrib. Comput. 2(3), 238\u2013249 (1985)","journal-title":"J. Parallel Distrib. Comput."}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-019-00351-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-019-00351-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-019-00351-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,29]],"date-time":"2020-05-29T19:29:10Z","timestamp":1590780550000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-019-00351-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,31]]},"references-count":48,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["351"],"URL":"https:\/\/doi.org\/10.1007\/s00446-019-00351-5","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,31]]},"assertion":[{"value":"15 January 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 March 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 May 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}