Multivariate analysis of orthogonal range searching and graph distances

DOI10.1007/s00453-020-00680-zzbMath1452.68134OpenAlexW3011484032MaRDI QIDQ786041

Thore Husfeldt, Måns Magnusson, Karl Bringmann

Publication date: 12 August 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-020-00680-z

zbMATH Keywords

diametertreewidthradiusWiener indexvertex cover numberorthogonal range searching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Distance in graphs (05C12) Data structures (68P05) Graphical indices (Wiener index, Zagreb index, Randi? index, etc.) (05C09)

Related Items (4)

Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ Beyond Helly graphs: the diameter problem on absolute retracts ⋮ Distance problems within Helly graphs and \(k\)-Helly graphs ⋮ Parameterized complexity of diameter

Cites Work

• Multidimensional divide-and-conquer
• Algorithms for graphs of bounded treewidth via orthogonal range searching
• Time bounds for selection
• Which problems have strongly exponential complexity?
• All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
• Vertex Cover: Further Observations and Further Improvements
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Lower bounds for orthogonal range searching: I. The reporting case
• Set Partitioning via Inclusion-Exclusion
• New Data Structures for Orthogonal Range Queries
• Combinatorial solutions of multidimensional divide-and-conquer recurrences
• Quintary trees
• Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
• Computing Graph Distances Parameterized by Treewidth and Diameter
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• Fast approximation algorithms for the diameter and radius of sparse graphs
• Parameterized complexity of diameter

This page was built for publication: Multivariate analysis of orthogonal range searching and graph distances