On the Existence of the Unique Shortest Path in Weighted ER Graphs
| Autor: | Yi-You Lin, 林奕佑 |
|---|---|
| Rok vydání: | 2019 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 107 Let $G=(V,E)$ be a simple undirected connected graph, $s$,$t\in V$ and $M\in\mathbb{Z}^+$. Pick a weight $w(e)$, where $e$ belongs to $E$, independently and uniformly at random from $\{1,2,\ldots,M\}. As can be seen from the result of Ta-Shma (2015),$$\Pr[\text{$G$ has a unique shortest $s$-$t$ path}]\geq \left(1-\frac{1}{M}\right)^{|E|}$$, where the length of a path is the sum of the weighs (w.r.t. $w$) of its constituent edges. The right-hand side of the above inequality is the best bound we know of. Through the experiments, we found that Erdős–Rényi random graph $G(n,p)$ has a unique shortest $s$-$t$ path with probability at least $(1.7\times 10^5)\times (1-1/M)^{|E|}$ for $p\in[0.1,0.9]$. So there must be a lot of room for improving the currently best lower bound on the probability of $G(n,p)$ having a unique shortest $s$-$t$ path. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|