Abstract | ||
---|---|---|
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 . (k + ([log n])(k) . 2(k) log n), where k is linear in the treewidth of the graph. For every epsilon > 0, this bound is n(1+epsilon)expO(k), which matches a hardness result of Abboud et al. (in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016. https://doi.org/10.1137/1.9781611974331.ch28) 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-824, 2009. https://doi.org/10.1016/j.comgeo.2009.02.001) 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 (6 + d([log n]) . 2, as originally observed by Monier (J Algorithms 1:60-74, 1980. https://doi.org/10.1016/0196-6774(80)90005-X). We also investigate the parameterization by vertex cover number. |
Year | DOI | Venue |
---|---|---|
2020 | 10.1007/s00453-020-00680-z | ALGORITHMICA |
Keywords | DocType | Volume |
Diameter,Radius,Wiener index,Orthogonal range searching,Treewidth,Vertex cover number | Journal | 82.0 |
Issue | ISSN | Citations |
SP8 | 0178-4617 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Karl Bringmann | 1 | 427 | 30.13 |
Thore Husfeldt | 2 | 733 | 40.87 |
Måns Magnusson | 3 | 16 | 2.47 |