Shortest Path Centrality and the APSP problem via VC-dimension and Rademacher Averages

Alane M. de Lima, Murilo V. G. da Silva, André L. Vignatti

In this paper we are interested in a version of the All-pairs Shortest Paths problem (APSP) that fits neither in the exact nor in the approximate case. We define a measure of centr…