Going Beyond Surfaces in Diameter Approximation

Michał Włodarczyk

Calculating the diameter of an undirected graph requires quadratic running time under the Strong Exponential Time Hypothesis and this barrier works even against any approximation b…