Multivariate Analysis of Orthogonal Range Searching and Graph Distances

Forskningsoutput: Kapitel i bok/rapport/Conference proceedingKonferenspaper i proceeding

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 * 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.

Detaljer

Författare
Enheter & grupper
Externa organisationer
  • Max Planck Institute For Informatics
  • IT University of Copenhagen
  • Lund University
Forskningsområden

Ämnesklassifikation (UKÄ) – OBLIGATORISK

  • Datavetenskap (datalogi)
Originalspråkengelska
Titel på värdpublikation13th International Symposium on Parameterized and Exact Computation, IPEC 2018
Undertitel på gästpublikationAugust 20-24, 2018, Helsinki, Finland
RedaktörerChristophe Paul, Michał Philipczuk
FörlagSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Sidor1–13
Antal sidor13
Volym115
ISBN (elektroniskt)978-3-95977-084-2
StatusPublished - 2019 feb 6
PublikationskategoriForskning
Peer review utfördJa
Evenemang13th International Symposium on Parameterized and Exact Computation (IPEC 2018). - Helsinki, Finland
Varaktighet: 2018 aug 202018 aug 24

Publikationsserier

NamnLIPIcs
FörlagSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Volym115

Konferens

Konferens13th International Symposium on Parameterized and Exact Computation (IPEC 2018).
LandFinland
OrtHelsinki
Period2018/08/202018/08/24

Related projects

Visa alla (1)