Multivariate Analysis of Orthogonal Range Searching and Graph Distances
(2020) In Algorithmica 82(8). p.2292-2315- 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+⌈logn⌉k)·2klogn), where k is linear in the treewidth of the graph. For every ϵ> 0 , this bound is n1 + ϵexp O(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... (More)
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+⌈logn⌉k)·2klogn), where k is linear in the treewidth of the graph. For every ϵ> 0 , this bound is n1 + ϵexp O(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 dn to (d+⌈logn⌉d), 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.
(Less)
- author
- Bringmann, Karl ; Husfeldt, Thore LU and Magnusson, Måns
- organization
- publishing date
- 2020-08
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Diameter, Orthogonal range searching, Radius, Treewidth, Vertex cover number, Wiener index
- in
- Algorithmica
- volume
- 82
- issue
- 8
- pages
- 24 pages
- publisher
- Springer
- external identifiers
-
- scopus:85082701786
- ISSN
- 0178-4617
- DOI
- 10.1007/s00453-020-00680-z
- language
- English
- LU publication?
- yes
- id
- e6de0824-7cac-448f-a781-4be994891bc7
- date added to LUP
- 2020-04-24 16:25:57
- date last changed
- 2022-04-18 21:51:04
@article{e6de0824-7cac-448f-a781-4be994891bc7, abstract = {{<p>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+⌈logn⌉k)·2klogn), where k is linear in the treewidth of the graph. For every ϵ> 0 , this bound is n<sup>1</sup> <sup>+</sup> <sup>ϵ</sup>exp O(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 <sup>d</sup>n to (d+⌈logn⌉d), 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.</p>}}, author = {{Bringmann, Karl and Husfeldt, Thore and Magnusson, Måns}}, issn = {{0178-4617}}, keywords = {{Diameter; Orthogonal range searching; Radius; Treewidth; Vertex cover number; Wiener index}}, language = {{eng}}, number = {{8}}, pages = {{2292--2315}}, publisher = {{Springer}}, series = {{Algorithmica}}, title = {{Multivariate Analysis of Orthogonal Range Searching and Graph Distances}}, url = {{http://dx.doi.org/10.1007/s00453-020-00680-z}}, doi = {{10.1007/s00453-020-00680-z}}, volume = {{82}}, year = {{2020}}, }