首页|Spanners in randomly weighted graphs: Independent edge lengths
Spanners in randomly weighted graphs: Independent edge lengths
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
? 2021 Elsevier B.V.Given a connected graph G=(V,E) and a length function ?:E→R we let dv,w denote the shortest distance between vertex v and vertex w. A t-spanner is a subset E′?E such that if dv,w′ denotes shortest distances in the subgraph G′=(V,E′) then dv,w′≤tdv,w for all v,w∈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 [Formula presented] edges and that this is best possible. In particular, our result applies to the random graphs Gn,p for np?logn.
Random edge lengthsShortest pathsSpanners
Frieze A.、Pegden W.
展开 >
Department of Mathematical Sciences Carnegie Mellon University
NSTL
Elsevier
