论文标题
添加随机加权边缘的效果
The effect of adding randomly weighted edges
论文作者
论文摘要
我们考虑以下问题。我们有一个密集的常规图$ g $，带有$αn$，其中$α> 0 $是一个常数。我们添加$ m = o（n^2）$随机边缘。增强图$ g（m）$的边缘被赋予独立边缘权重$ x（e）$，$ e \ in E（g（m））$。我们估计一些指定组合结构的最小重量。我们表明，在某些情况下，我们可以获得与完整图的相同估计值，但按因子$α^{ - 1} $缩放。我们考虑跨越树木，最短路径，（伪随机）两部分图中的完美匹配。
We consider the following question. We have a dense regular graph $G$ with degree $αn$, where $α>0$ is a constant. We add $m=o(n^2)$ random edges. The edges of the augmented graph $G(m)$ are given independent edge weights $X(e)$, $e\in E(G(m))$. We estimate the minimum weight of some specified combinatorial structures. We show that in certain cases, we can obtain the same estimate as is known for the complete graph, but scaled by a factor $α^{-1}$. We consider spanning trees, shortest paths, perfect matchings in (pseudo-random) bipartite graphs.
