Certificates in P and Subquadratic-Time Computation of Radius, Diameter, and all Eccentricities in Graphs

Feodor F. Dragan, Guillaume Ducoffe, Michel Habib +1

In the context of fine-grained complexity, we investigate the notion of certificate enabling faster polynomial-time algorithms. We specifically target radius (minimum eccentricity)…