Multivariate analysis of orthogonal range searching and graph distances
From MaRDI portal
(Redirected from Publication:786041)
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)
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
Cites work
- A \(c^k n\) 5-approximation algorithm for treewidth
- Algorithms for graphs of bounded treewidth via orthogonal range searching
- All-pairs shortest paths with real weights in \(O ( n^{3}/\log n )\) time
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Combinatorial solutions of multidimensional divide-and-conquer recurrences
- Computing graph distances parameterized by treewidth and diameter
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- Lower bounds for orthogonal range searching: I. The reporting case
- Multidimensional divide-and-conquer
- New Data Structures for Orthogonal Range Queries
- Parameterized complexity of diameter
- Quintary trees
- Set partitioning via inclusion-exclusion
- Time bounds for selection
- Vertex cover: Further observations and further improvements
- Which problems have strongly exponential complexity?
Cited in
(7)- Computing graph distances parameterized by treewidth and diameter
- 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
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)
