{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,2]],"date-time":"2026-02-02T19:53:06Z","timestamp":1770061986171,"version":"3.49.0"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2020,3,14]],"date-time":"2020-03-14T00:00:00Z","timestamp":1584144000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,3,14]],"date-time":"2020-03-14T00:00:00Z","timestamp":1584144000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100008398","name":"Villum Fonden","doi-asserted-by":"crossref","award":["16582"],"award-info":[{"award-number":["16582"]}],"id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100004359","name":"Vetenskapsr\u00e5det","doi-asserted-by":"crossref","award":["VR-2016-03855"],"award-info":[{"award-number":["VR-2016-03855"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,8]]},"abstract":"Abstract<\/jats:title>We show that the eccentricities, diameter, radius, and Wiener index of an undirected n<\/jats:italic>-vertex graph with nonnegative edge lengths can be computed in time $$O(n\\cdot \\left( {\\begin{array}{c}k+\\lceil \\log n\\rceil \\\\ k\\end{array}}\\right) \\cdot 2^k \\log n)$$<\/jats:tex-math>\n\nO<\/mml:mi>\n(<\/mml:mo>\nn<\/mml:mi>\n\u00b7<\/mml:mo>\n\n\n\n\n\n\nk<\/mml:mi>\n+<\/mml:mo>\n\u2308<\/mml:mo>\nlog<\/mml:mo>\nn<\/mml:mi>\n\u2309<\/mml:mo>\n<\/mml:mrow>\n<\/mml:mtd>\n<\/mml:mtr>\n\n\n\n\nk<\/mml:mi>\n<\/mml:mrow>\n<\/mml:mtd>\n<\/mml:mtr>\n<\/mml:mtable>\n<\/mml:mrow>\n<\/mml:mfenced>\n\u00b7<\/mml:mo>\n\n2<\/mml:mn>\nk<\/mml:mi>\n<\/mml:msup>\nlog<\/mml:mo>\nn<\/mml:mi>\n)<\/mml:mo>\n<\/mml:mrow>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where k<\/jats:italic> is linear in the treewidth of the graph. For every $$\\epsilon >0$$<\/jats:tex-math>\n\n\u03f5<\/mml:mi>\n><\/mml:mo>\n0<\/mml:mn>\n<\/mml:mrow>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula>, this bound is $$n^{1+\\epsilon }\\exp O(k)$$<\/jats:tex-math>\n\n\nn<\/mml:mi>\n\n1<\/mml:mn>\n+<\/mml:mo>\n\u03f5<\/mml:mi>\n<\/mml:mrow>\n<\/mml:msup>\nexp<\/mml:mo>\nO<\/mml:mi>\n\n(<\/mml:mo>\nk<\/mml:mi>\n)<\/mml:mo>\n<\/mml:mrow>\n<\/mml:mrow>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula>, which matches a hardness result of Abboud et al. (in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016. 10.1137\/1.9781611974331.ch28<\/jats:ext-link>) and closes an open problem in the multivariate analysis of polynomial-time computation. To this end, we show that the analysis of an algorithm of Cabello and Knauer (Comput Geom 42:815\u2013824, 2009. 10.1016\/j.comgeo.2009.02.001<\/jats:ext-link>) in the regime of non-constant treewidth can be improved by revisiting the analysis of orthogonal range searching, improving bounds of the form $$\\log ^d n$$<\/jats:tex-math>\n\n\nlog<\/mml:mo>\nd<\/mml:mi>\n<\/mml:msup>\nn<\/mml:mi>\n<\/mml:mrow>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula> to $$\\left( {\\begin{array}{c}d+\\lceil \\log n\\rceil \\\\ d\\end{array}}\\right)$$<\/jats:tex-math>\n\n\n\n\n\n\nd<\/mml:mi>\n+<\/mml:mo>\n\u2308<\/mml:mo>\nlog<\/mml:mo>\nn<\/mml:mi>\n\u2309<\/mml:mo>\n<\/mml:mrow>\n<\/mml:mtd>\n<\/mml:mtr>\n\n\n\n\nd<\/mml:mi>\n<\/mml:mrow>\n<\/mml:mtd>\n<\/mml:mtr>\n<\/mml:mtable>\n<\/mml:mrow>\n<\/mml:mfenced>\n<\/mml:math><\/jats:alternatives><\/jats:inline-formula>, as originally observed by Monier (J Algorithms 1:60\u201374, 1980. 10.1016\/0196-6774(80)90005-X<\/jats:ext-link>). We also investigate the parameterization by vertex cover number.<\/jats:p>","DOI":"10.1007\/s00453-020-00680-z","type":"journal-article","created":{"date-parts":[[2020,3,14]],"date-time":"2020-03-14T09:03:04Z","timestamp":1584176584000},"page":"2292-2315","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Multivariate Analysis of Orthogonal Range Searching and Graph Distances"],"prefix":"10.1007","volume":"82","author":[{"given":"Karl","family":"Bringmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9078-4512","authenticated-orcid":false,"given":"Thore","family":"Husfeldt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M\u00e5ns","family":"Magnusson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,3,14]]},"reference":[{"key":"680_CR1","doi-asserted-by":"publisher","unstructured":"Abboud, A., Williams, V.V., Wang, J.R.: Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In: Proceedings of the Twenty-Seventh Annual ACM\u2013SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10\u201312 (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch28","DOI":"10.1137\/1.9781611974331.ch28"},{"key":"680_CR2","doi-asserted-by":"crossref","unstructured":"Bentert, M., Nichterlein, A.: Parameterized complexity of diameter. CoRR, arXiv:1802.10048 (2018)","DOI":"10.1007\/978-3-030-17402-6_5"},{"issue":"4","key":"680_CR3","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1145\/358841.358850","volume":"23","author":"JL Bentley","year":"1980","unstructured":"Bentley, J.L.: Multidimensional divide-and-conquer. Commun. ACM 23(4), 214\u2013229 (1980). https:\/\/doi.org\/10.1145\/358841.358850","journal-title":"Commun. ACM"},{"issue":"2","key":"680_CR4","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1137\/070683933","volume":"39","author":"A Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM J. Comput. 39(2), 546\u2013563 (2009)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"680_CR5","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M Blum","year":"1973","unstructured":"Blum, M., Floyd, R.W., Pratt, V.R., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. J. Comput. Syst. Sci. 7(4), 448\u2013461 (1973). https:\/\/doi.org\/10.1016\/S0022-0000(73)80033-9","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"680_CR6","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1137\/130947374","volume":"45","author":"HL Bodlaender","year":"2016","unstructured":"Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: An $${O}(c^k n)$$ 5-approximation algorithm for treewidth. SIAM J. Comput 45(2), 317\u2013378 (2016). https:\/\/doi.org\/10.1137\/130947374","journal-title":"SIAM J. Comput"},{"issue":"9","key":"680_CR7","doi-asserted-by":"publisher","first-page":"815","DOI":"10.1016\/j.comgeo.2009.02.001","volume":"42","author":"S Cabello","year":"2009","unstructured":"Cabello, S., Knauer, C.: Algorithms for bounded treewidth with orthogonal range searching. Comput. Geom. 42(9), 815\u2013824 (2009). https:\/\/doi.org\/10.1016\/j.comgeo.2009.02.001","journal-title":"Comput. Geom."},{"issue":"2","key":"680_CR8","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/s00453-007-9062-1","volume":"50","author":"TM Chan","year":"2008","unstructured":"Chan, T.M.: All-pairs shortest paths with real weights in $${O}(n^3\/\\log n)$$ time. Algorithmica 50(2), 236\u2013243 (2008). https:\/\/doi.org\/10.1007\/s00453-007-9062-1","journal-title":"Algorithmica"},{"issue":"2","key":"680_CR9","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1145\/77600.77614","volume":"37","author":"B Chazelle","year":"1990","unstructured":"Chazelle, B.: Lower bounds for orthogonal range searching: I. The reporting case. J. Assoc. Comput. Mach 37(2), 200\u2013212 (1990). https:\/\/doi.org\/10.1145\/77600.77614","journal-title":"J. Assoc. Comput. Mach"},{"key":"680_CR10","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1006\/jagm.2001.1186","volume":"41","author":"J Chen","year":"2001","unstructured":"Chen, J., Kanj, I.A., Jia, W.: Vertex cover: Further observations and further improvements. J. Algorithms 41, 280\u2013301 (2001). https:\/\/doi.org\/10.1006\/jagm.2001.1186","journal-title":"J. Algorithms"},{"key":"680_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999)"},{"key":"680_CR12","doi-asserted-by":"publisher","unstructured":"Husfeldt, T.: Computing graph distances parameterized by treewidth and diameter. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016), volume 63 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 16:1\u201316:11, Dagstuhl, Germany. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik (2017). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2016.16 (2017)","DOI":"10.4230\/LIPIcs.IPEC.2016.16"},{"issue":"4","key":"680_CR13","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001). https:\/\/doi.org\/10.1006\/jcss.2001.1774","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"680_CR14","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1145\/320613.320618","volume":"5","author":"D-T Lee","year":"1980","unstructured":"Lee, D.-T., Wong, C.K.: Quintary trees: a file structure for multidimensional database systems. ACM Trans. Database Syst. 5(3), 339\u2013353 (1980). https:\/\/doi.org\/10.1145\/320613.320618","journal-title":"ACM Trans. Database Syst."},{"key":"680_CR15","doi-asserted-by":"publisher","unstructured":"Lueker, G.S.: A data structure for orthogonal range queries. In: 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Michigan, USA, 16\u201318 October 1978, pp 28\u201334. IEEE Computer Society (1978). https:\/\/doi.org\/10.1109\/SFCS.1978.1","DOI":"10.1109\/SFCS.1978.1"},{"issue":"1","key":"680_CR16","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/0196-6774(80)90005-X","volume":"1","author":"L Monier","year":"1980","unstructured":"Monier, L.: Combinatorial solutions of multidimensional divide-and-conquer recurrences. J. Algorithms 1(1), 60\u201374 (1980). https:\/\/doi.org\/10.1016\/0196-6774(80)90005-X","journal-title":"J. Algorithms"},{"key":"680_CR17","doi-asserted-by":"publisher","unstructured":"Roditty, L., Williams, V.V.: Fast approximation algorithms for the diameter and radius of sparse graphs. In: Symposium on Theory of Computing Conference, STOC\u201913, Palo Alto, CA, USA, June 1\u20134, 2013, pp. 515\u2013524 (2013). https:\/\/doi.org\/10.1145\/2488608.2488673","DOI":"10.1145\/2488608.2488673"},{"key":"680_CR18","unstructured":"Shi, Q.: Efficient algorithms for network center\/covering location optimization problems. PhD thesis, School of Computing Science, Simon Fraser University (2008)"},{"issue":"1","key":"680_CR19","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1137\/0214019","volume":"14","author":"DE Willard","year":"1985","unstructured":"Willard, D.E.: New data structures for orthogonal range queries. SIAM J. Comput. 14(1), 232\u2013253 (1985). https:\/\/doi.org\/10.1137\/0214019","journal-title":"SIAM J. Comput."},{"key":"680_CR20","doi-asserted-by":"publisher","unstructured":"Williams, V.V.: Hardness of easy problems: basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). In 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, September 16\u201318, 2015, Patras, Greece, pp. 17\u201329 (2015). https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2015.17","DOI":"10.4230\/LIPIcs.IPEC.2015.17"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00680-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00680-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00680-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,14]],"date-time":"2021-03-14T00:51:23Z","timestamp":1615683083000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00680-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,14]]},"references-count":20,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2020,8]]}},"alternative-id":["680"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00680-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,14]]},"assertion":[{"value":"27 November 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 January 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 March 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}