Better diameter algorithms for bounded VC-dimension graphs and geometric intersection graphs
From MaRDI portal
Cites work
- 4 vs 7 Sparse Undirected Unweighted Diameter Is SETH-hard at Time n 4/3
- A combinatorial problem; stability and order for models and theories in infinitary languages
- A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
- A simple linear-time algorithm for computing the center of an interval graph
- All-pairs shortest paths in geometric intersection graphs
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Better approximation algorithms for the graph diameter
- Computation of the center and diameter of outerplanar graphs
- Covering planar graphs with a fixed number of balls
- Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension
- Diameter determination on restricted graph families
- Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Hardness of approximate diameter: now for undirected graphs
- scientific article; zbMATH DE number 6861957 (Why is no real title available?)
- New bounds for approximating extremal distances in undirected graphs
- On diameter approximation in directed graphs
- On the complexity of k-SAT
- On the density of families of sets
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Quasi-optimal range searching in spaces of finite VC-dimension
- Settling SETH vs. approximate sparse directed unweighted diameter (up to (NU)NSETH)
- Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs
- The VC dimension of \(k\)-fold union
- Tight conditional lower bounds for approximating diameter in directed graphs
- Towards sub-quadratic diameter computation in geometric intersection graphs
- VC-dimension and Erdős-Pósa property
- Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
This page was built for publication: Better diameter algorithms for bounded VC-dimension graphs and geometric intersection graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7253109)
