Multivariate analysis of orthogonal range searching and graph distances
DOI10.1007/S00453-020-00680-ZzbMATH Open1452.68134OpenAlexW3011484032MaRDI QIDQ786041FDOQ786041
Authors: Karl Bringmann, Thore Husfeldt, Måns Magnusson 
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
Recommendations
- Multivariate analysis of orthogonal range searching and graph distances
- Computing graph distances parameterized by treewidth and diameter
- Algorithms for graphs of bounded treewidth via orthogonal range searching
- Diameter, eccentricities and distance oracle computations on \(H\)-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
- Better approximation algorithms for the graph diameter
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Graphical indices (Wiener index, Zagreb index, Randi? index, etc.) (05C09) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Distance in graphs (05C12)
Cites Work
- Multidimensional divide-and-conquer
- Which problems have strongly exponential complexity?
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Set partitioning via inclusion-exclusion
- Time bounds for selection
- Vertex cover: Further observations and further improvements
- Lower bounds for orthogonal range searching: I. The reporting case
- New Data Structures for Orthogonal Range Queries
- Algorithms for graphs of bounded treewidth via orthogonal range searching
- A \(c^k n\) 5-approximation algorithm for treewidth
- All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
- 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)
- Parameterized complexity of diameter
Cited In (7)
- Multivariate analysis of orthogonal range searching and graph distances
- Diameter, eccentricities and distance oracle computations on \(H\)-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
- Parameterized complexity of streaming diameter and connectivity problems
- Parameterized complexity of diameter
- Beyond Helly graphs: the diameter problem on absolute retracts
- Distance problems within Helly graphs and \(k\)-Helly graphs
- Computing graph distances parameterized by treewidth and diameter
This page was built for publication: Multivariate analysis of orthogonal range searching and graph distances
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q786041)
