Spanners in randomly weighted graphs: independent edge lengths

DOI10.1016/J.DAM.2021.11.009zbMATH Open1480.05068arXiv2105.01718OpenAlexW3215689807MaRDI QIDQ2065765FDOQ2065765

Authors: Wesley Pegden, Alan Frieze 

Publication date: 13 January 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: Given a connected graph $G=(V,E)$ and a length function $ell:EomathbbR$ we let $d_{v,w}$ denote the shortest distance between vertex $v$ and vertex $w$. A $t$-spanner is a subset $E^{\prime }subseteqE$ such that if $d{\text{'}}_{v,w}$ denotes shortest distances in the subgraph $G^{\prime }=(V,E^{\prime })$ then $d{\text{'}}_{v,w}leqt{d}_{v,w}$ for all $v,winV$. 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 $approxfrac12nlogn$ edges and that this is best possible. In particular, our result applies to the random graphs $G_{n,p}$ for $npgglogn$.

Full work available at URL: https://arxiv.org/abs/2105.01718

Recommendations

• Spanners in randomly weighted graphs: Euclidean case
• Spanners in graphs of bounded degree
• NEW SPARSENESS RESULTS ON GRAPH SPANNERS
• scientific article; zbMATH DE number 2038725
• Light spanners

zbMATH Keywords

shortest pathsspannersrandom edge lengths

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Distance in graphs (05C12) Signed and weighted graphs (05C22) Paths and cycles (05C38)

Cites Work

• A note on two problems in connexion with graphs
• One, Two and Three Times log n/n for Paths in a Complete Graph with Random Weights
• Weak disorder asymptotics in the stochastic mean-field model of distance
• Graph spanners: a tutorial review
• Traveling in randomly embedded random graphs
• The effect of adding randomly weighted edges

Cited In (1)

• Spanners in randomly weighted graphs: Euclidean case

This page was built for publication: Spanners in randomly weighted graphs: independent edge lengths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2065765)