Spanners in randomly weighted graphs: Independent edge lengths

Given a connected graph G = (V, E) and a length function l : E -> R we let d(v,w) denote the shortest distance between vertex v and vertex w. A t-spanner is a subset E' subset of E such that if d(v,w)' denotes shortest distances in the subgraph G' = (V, E') then d(v,w)' <= td(v,w) for all v, w is an element of V. We show that for a large class of graphs with suitable degree and expansion properties with independent exponential mean one edge lengths, there is w.h.p. a 1-spanner that uses approximate to 1/2nlog n edges and that this is best possible. In particular, our result applies to the random graphs G(n,p )for np >> log n. (C) 2021 Elsevier B.V. All rights reserved.