The effect of adding randomly weighted edges

2020/04/27 by Frieze, Alan · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2004.12986

Abstract

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²) random edges. The edges of the augmented graph G(m) are given independent edge weights X(e), e∈ 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.

Cited by

• Karp's patching algorithm on dense digraph

Related

• On the random minimum edge-disjoint spanning trees problem
• Shortest-weight paths in random regular graphs
• Approximating the Statistics of various Properties in Randomly Weighted Graphs
• Graph Sparsification by Edge-Connectivity and Random Spanning Trees
• Testing Dependency of Weighted Random Graphs