{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:05:56Z","timestamp":1750694756856,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T00:00:00Z","timestamp":1583712000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ISF","award":["1528\/15, 724\/15, and 1817\/17"],"award-info":[{"award-number":["1528\/15, 724\/15, and 1817\/17"]}]},{"name":"BSF","award":["2015813"],"award-info":[{"award-number":["2015813"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2020,4,30]]},"abstract":"<jats:p>\n            The\n            <jats:italic>metric Ramsey problem<\/jats:italic>\n            asks for the largest subset\n            <jats:italic>S<\/jats:italic>\n            of a metric space that can be embedded into an ultrametric (more generally into a Hilbert space) with a given distortion. Study of this problem was motivated as a non-linear version of Dvoretzky theorem. Mendel and Naor [29] devised the so-called Ramsey Partitions to address this problem, and showed the algorithmic applications of their techniques to approximate distance oracles and ranking problems.\n          <\/jats:p>\n          <jats:p>\n            In this article, we study the natural extension of the metric Ramsey problem to graphs, and introduce the notion of\n            <jats:italic>Ramsey Spanning Trees<\/jats:italic>\n            . We ask for the largest subset\n            <jats:italic>S<\/jats:italic>\n            \u2286\n            <jats:italic>V<\/jats:italic>\n            of a given graph\n            <jats:italic>G<\/jats:italic>\n            =(\n            <jats:italic>V<\/jats:italic>\n            ,\n            <jats:italic>E<\/jats:italic>\n            ), such that there exists a spanning tree of\n            <jats:italic>G<\/jats:italic>\n            that has small stretch for\n            <jats:italic>S<\/jats:italic>\n            . Applied iteratively, this provides a small collection of spanning trees, such that each vertex has a tree providing low stretch paths to\n            <jats:italic>all other vertices<\/jats:italic>\n            . The union of these trees serves as a special type of spanner, a\n            <jats:italic>tree-padding spanner<\/jats:italic>\n            . We use this spanner to devise the first compact stateless routing scheme with\n            <jats:italic>O<\/jats:italic>\n            (1) routing decision time, and labels that are much shorter than in all currently existing schemes.\n          <\/jats:p>\n          <jats:p>\n            We first revisit the metric Ramsey problem and provide a new deterministic construction. We prove that for every\n            <jats:italic>k<\/jats:italic>\n            , any\n            <jats:italic>n<\/jats:italic>\n            -point metric space has a subset\n            <jats:italic>S<\/jats:italic>\n            of size at least\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              1\u22121\/\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            that embeds into an ultrametric with distortion 8\n            <jats:italic>k<\/jats:italic>\n            . We use this result to obtain the state-of-the-art deterministic construction of a distance oracle. Building on this result, we prove that for every\n            <jats:italic>k<\/jats:italic>\n            , any\n            <jats:italic>n<\/jats:italic>\n            -vertex graph\n            <jats:italic>G<\/jats:italic>\n            =(\n            <jats:italic>V<\/jats:italic>\n            ,\n            <jats:italic>E<\/jats:italic>\n            ) has a subset\n            <jats:italic>S<\/jats:italic>\n            of size at least\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              1\u22121\/\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            , and a spanning tree of\n            <jats:italic>G<\/jats:italic>\n            , that has stretch\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            log log\n            <jats:italic>n<\/jats:italic>\n            ) between any point in\n            <jats:italic>S<\/jats:italic>\n            and any point in\n            <jats:italic>V<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/3371039","type":"journal-article","created":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T21:33:40Z","timestamp":1583789620000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Ramsey Spanning Trees and Their Applications"],"prefix":"10.1145","volume":"16","author":[{"given":"Ittai","family":"Abraham","sequence":"first","affiliation":[{"name":"VMWare, Herzliya, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shiri","family":"Chechik","sequence":"additional","affiliation":[{"name":"Tel-Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Elkin","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Beer Sheva, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arnold","family":"Filtser","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Beer Sheva, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ofer","family":"Neiman","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Beer Sheva, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,3,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897555"},{"volume-title":"Proceedings of the 34th Annual Symposium on Foundations of Computer Science","year":"1993","author":"Awerbuch Baruch","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Ingo Alth\u00f6fer Gautam Das David P. Dobkin and Deborah Joseph. 1990. Generating sparse spanners for weighted graphs. In SWAT. 26--37.  Ingo Alth\u00f6fer Gautam Das David P. Dobkin and Deborah Joseph. 1990. Generating sparse spanners for weighted graphs. In SWAT. 26--37.","DOI":"10.1007\/3-540-52846-6_75"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792224474"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214015"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89571"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808722"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30140-0_10"},{"key":"e_1_2_1_9_1","unstructured":"Yair Bartal. 2011. Lecture notes in Metric Embedding Theory and Its Algorithmic Applications. Retrieved from http:\/\/moodle.cs.huji.ac.il\/cs10\/file.php\/67720\/GM_Lecture6.pdf.  Yair Bartal. 2011. Lecture notes in Metric Embedding Theory and Its Algorithmic Applications. Retrieved from http:\/\/moodle.cs.huji.ac.il\/cs10\/file.php\/67720\/GM_Lecture6.pdf."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.05.008"},{"volume-title":"Bender and Martin Farach-Colton","year":"2000","author":"Michael","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02801990"},{"volume-title":"A new efficient construction on probabilistic tree embeddings. CoRR abs\/1605.04651","year":"2016","author":"Blelloch Guy E.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Y. Bartal N. Linial M. Mendel and A. Naor. 2003. On metric Ramsey-type phenomena. In STOC. 463--472.  Y. Bartal N. Linial M. Mendel and A. Naor. 2003. On metric Ramsey-type phenomena. In STOC. 463--472.","DOI":"10.1145\/780542.780610"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-004-1100-z"},{"volume":"2719","volume-title":"Proceedings of the 30th International Colloquium on Automata, Languages and Programming (LNCS)","author":"Baswana S.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2484268"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591801"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746562"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701395978"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366822"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060665"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/383962.383983"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701393384"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780608"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"volume-title":"Last but not least: Online spanners for buy-at-bulk. CoRR abs\/1611.00052","year":"2016","author":"Gupta Anupam","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4171\/JEMS\/79"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-012-0039-7"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_22"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200760"},{"volume-title":"Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC). Hersonissos","author":"Thorup M.","key":"e_1_2_1_34_1"},{"volume-title":"Proceedings of the 13th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA). ACM Press, 1--10","author":"Thorup M.","key":"e_1_2_1_35_1"},{"volume-title":"Proceedings of Symp. on Discr. Algorithms. 802--809","author":"Thorup M.","key":"e_1_2_1_36_1"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.39"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3371039","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3371039","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:36Z","timestamp":1750202616000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3371039"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,9]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,4,30]]}},"alternative-id":["10.1145\/3371039"],"URL":"https:\/\/doi.org\/10.1145\/3371039","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2020,3,9]]},"assertion":[{"value":"2018-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-03-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}