Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Multivariate Analysis of Orthogonal Range Searching and Graph Distances

Bringmann, Karl ; Husfeldt, Thore LU and Magnusson, Måns (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)
Please use this url to cite or link to this publication:
author
; and
organization
publishing date
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 ϵ&gt; 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}},
}