| Autor: |
Houda Lotfi, Jean-Michel Fourneau, Edouard Longueville, Yann Ben Maissa, Loubna Echabbi |
| Rok vydání: |
2021 |
| Předmět: |
|
| Zdroj: |
Lecture Notes in Computer Science ISBN: 9783030918248 |
| DOI: |
10.1007/978-3-030-91825-5_8 |
| Popis: |
We consider a stochastic network where the arcs are associated to discrete random variables which represent the delay. We need to compute the shortest delay (or equivalently the distance) from the source to the sink in the network. Due to the randomness, this problem is known to be hard while it has many polynomial algorithms when the arcs have deterministic lengths (or durations). We provide three approaches and we prove algorithms to obtain stochastic bounds for the distribution of the distance. We present several examples to compare the precision and the time. The approach based on the association of random variables gives very accurate results on the examples and has the smallest complexity. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
