加载中…
We show, assuming the Strong Exponential Time Hypothesis, that for every , approximating undirected unweighted Diameter on -vertex -edge graphs within ratio requires $n^{4/3 - o(1)}$ time. This is the first result that conditionally rules out a near-linear time -approximation for undirected Diameter.

生成讲解博客的中文版本

生成AI智能校验的中文版本