Articles by Giannos Stamoulis

Faster diameter computation in graphs of bounded Euler genus

-- Giannos Stamoulis (CNRS, IRIF)

Roditty and Vassilevska-Williams [STOC 2013] showed that computing the diameter, i.e., farthest distance between any two vertices, of an (unweighted, undirected) graph cannot be done in subquadratic time unless the Strong Exponential Time Hypothesis fails. In a breakthrough work, Cabello [TALG 2019] showed a subquadratic algorithm in planar graphs ...