The effect of adding randomly weighted edges
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2020
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911563817943040 |
|---|---|
| author | Frieze, Alan |
| author_facet | Frieze, Alan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2004_12986 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | The effect of adding randomly weighted edges Frieze, Alan Combinatorics 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. |
| title | The effect of adding randomly weighted edges |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2004.12986 |