Deutsch
 
Benutzerhandbuch Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Forschungspapier

Multivariate Analysis of Orthogonal Range Searching and Graph Distances Parameterized by Treewidth

MPG-Autoren
/persons/resource/persons44182

Bringmann,  Karl
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

arXiv:1805.07135.pdf
(Preprint), 561KB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Bringmann, K., Husfeldt, T., & Magnusson, M. (2018). Multivariate Analysis of Orthogonal Range Searching and Graph Distances Parameterized by Treewidth. Retrieved from http://arxiv.org/abs/1805.07135.


Zitierlink: http://hdl.handle.net/21.11116/0000-0002-173B-3
Zusammenfassung
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\cdot \binom{k+\lceil\log n\rceil}{k} \cdot 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+\lceil\log n\rceil}{d}$, as originally observed by Monier (J. Alg. 1980). We also investigate the parameterization by vertex cover number.