2026-07-25T03:00:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10205 2024-03-06T10:44:15Z ddc:004 open_access

Multivariate Analysis of Orthogonal Range Searching and Graph Distances Bringmann, Karl Husfeldt, Thore Magnusson, Måns Diameter radius Wiener index orthogonal range searching treewidth vertex cover number We show that the eccentricities, diameter, radius, and Wiener index of an undirected n-vertex graph with nonnegative edge lengths can be computed in time O(n * binom{k+ceil[log n]}{k} * 2^k k^2 log n), where k is the treewidth of the graph. For every epsilon>0, this bound is n^{1+epsilon}exp O(k), which matches a hardness result of Abboud, Vassilevska Williams, and Wang (SODA 2015) 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 (Comp. Geom., 2009) 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 to binom{d+ceil[log n]}{d}, as originally observed by Monier (J. Alg. 1980). We also investigate the parameterization by vertex cover number. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Karl Bringmann and Thore Husfeldt and Måns Magnusson 2019 Is Part Of LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2018.4 urn:nbn:de:0030-drops-102050 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.4 eng https://creativecommons.org/licenses/by/3.0/legalcode