Spanners in randomly weighted graphs: Euclidean case
Spanners in randomly weighted graphs: Euclidean case
复制标题
随机加权图中的扳手：欧几里得案例
DOI：
10.1002/jgt.22950
复制
发表时间：
2023
影响因子：
0.9
通讯作者：
Pegden, Wesley
中科院分区：
文献类型：
--
作者：
Frieze, Alan;Pegden, Wesley
Given a connected graph G=(V,E) $G=(V,E)$ and a length function ℓ:E→R $\ell :E\to {\mathbb{R}}$ we let dv,w ${d}_{v,w}$ denote the shortest distance between vertex v $v$ and vertex w $w$. A t $t$‐spanner is a subset E′⊆E $E^{\prime} \subseteq E$ such that if dv,w′ ${d}_{v,w}^{^{\prime} }$ denotes shortest distances in the subgraph G′=(V,E′) $G^{\prime} =(V,E^{\prime} )$ then dv,w′≤tdv,w ${d}_{v,w}^{^{\prime} }\le t{d}_{v,w}$ for all v,w∈V $v,w\in V$. We study the size of spanners in the following scenario: we consider a random embedding Xp ${{\mathscr{X}}}_{p}$ of Gn,p ${G}_{n,p}$ into the unit square with Euclidean edge lengths. For ϵ>0 $\epsilon \gt 0$ constant, we prove the existence w.h.p. of (1+ϵ) $(1+\epsilon )$‐spanners for Xp ${{\mathscr{X}}}_{p}$ that have Oϵ(n) ${O}_{\epsilon }(n)$ edges. These spanners can be constructed in Oϵ(n2logn) ${O}_{\epsilon }({n}^{2}\mathrm{log}n)$ time. (We will use Oϵ ${O}_{\epsilon }$ to indicate that the hidden constant depends on ε $\varepsilon $). There are constraints on p $p$ preventing it going to zero too quickly.
Given a connected graph G=(V,E) $G=(V,E)$ and a length function ℓ:E→R $\ell :E\to {\mathbb{R}}$ we let dv,w ${d}_{v,w}$ denote the shortest distance between vertex v $v$ and vertex w $w$. A t $t$‐spanner is a subset E′⊆E $E^{\prime} \subseteq E$ such that if dv,w′ ${d}_{v,w}^{^{\prime} }$ denotes shortest distances in the subgraph G′=(V,E′) $G^{\prime} =(V,E^{\prime} )$ then dv,w′≤tdv,w ${d}_{v,w}^{^{\prime} }\le t{d}_{v,w}$ for all v,w∈V $v,w\in V$. We study the size of spanners in the following scenario: we consider a random embedding Xp ${{\mathscr{X}}}_{p}$ of Gn,p ${G}_{n,p}$ into the unit square with Euclidean edge lengths. For ϵ>0 $\epsilon \gt 0$ constant, we prove the existence w.h.p. of (1+ϵ) $(1+\epsilon )$‐spanners for Xp ${{\mathscr{X}}}_{p}$ that have Oϵ(n) ${O}_{\epsilon }(n)$ edges. These spanners can be constructed in Oϵ(n2logn) ${O}_{\epsilon }({n}^{2}\mathrm{log}n)$ time. (We will use Oϵ ${O}_{\epsilon }$ to indicate that the hidden constant depends on ε $\varepsilon $). There are constraints on p $p$ preventing it going to zero too quickly.
登录
查看更多内容
在随机嵌入的随机图中旅行
影响因子：
1
作者：
A. Frieze;W. Pegden
通讯作者：
W. Pegden
具有成本约束的最短路径：概率分析
影响因子：
1.1
作者：
Frieze, Alan;Tkocz, Tomasz
通讯作者：
Tkocz, Tomasz
A·哈贝：（1989）
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
通讯作者：
--
随机加权图中的扳手：独立的边长
影响因子：
1.1
作者：
Frieze, A.;Pegden, W.
通讯作者：
Pegden, W.
关于随机嵌入随机图的拉伸因子
影响因子：
0.8
作者：
Abbas Mehrabian;N. Wormald
通讯作者：
N. Wormald