Using random spanning trees in survivable networks design
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915635036946432 |
|---|---|
| author | Wrobel, Blazej Bojko, Dominik |
| author_facet | Wrobel, Blazej Bojko, Dominik |
| contents | We investigate a process of joining $k$ random spanning trees on a fixed clique $K_n$. The joined trees may not be disjoint and multiple edges are replaced by one simple edge. This process produces a simple graph $G$ on $n$~vertices with an edge set, which is a union of edge sets of the joined trees. We study a random variable $S_{k}$ of the number of edges in the generated graph $G$. The exact formula is derived for the expected value of the random variable $S_{k}$. In addition, an upper bound on the concentration coefficient of the random variable $S_{k}$ is provided. We use results of our analysis to design an algorithm to generate $k$-edge connected graphs for arbitrarily large values of $k \geq 2$. The designed algorithm solves a particular case of the Survivable Network Design Problem, where the cost of each edge is $c_{e} = 1$ and the connectivity requirement for each pair of vertices $u, v \in V(G)$ is $k$.The proposed algorithm is within a factor strictly less than $2$ of the optimal value (i.e., the number of edges in the generated graph) and its running time is $O(kn\log{n})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_19018 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Using random spanning trees in survivable networks design Wrobel, Blazej Bojko, Dominik Discrete Mathematics Data Structures and Algorithms We investigate a process of joining $k$ random spanning trees on a fixed clique $K_n$. The joined trees may not be disjoint and multiple edges are replaced by one simple edge. This process produces a simple graph $G$ on $n$~vertices with an edge set, which is a union of edge sets of the joined trees. We study a random variable $S_{k}$ of the number of edges in the generated graph $G$. The exact formula is derived for the expected value of the random variable $S_{k}$. In addition, an upper bound on the concentration coefficient of the random variable $S_{k}$ is provided. We use results of our analysis to design an algorithm to generate $k$-edge connected graphs for arbitrarily large values of $k \geq 2$. The designed algorithm solves a particular case of the Survivable Network Design Problem, where the cost of each edge is $c_{e} = 1$ and the connectivity requirement for each pair of vertices $u, v \in V(G)$ is $k$.The proposed algorithm is within a factor strictly less than $2$ of the optimal value (i.e., the number of edges in the generated graph) and its running time is $O(kn\log{n})$. |
| title | Using random spanning trees in survivable networks design |
| topic | Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.19018 |