[Zurück]

A. Panholzer, M. Kuba:
"Combinatorial Analysis of Growth Models for Series-Parallel Networks";
Vortrag: 27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, Krakow, Polen, 4-8. Juli 2016, Krakau, Polen (eingeladen); 04.07.2016 - 08.07.2016; in: "Proceedings of the 27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms, Krakow, Polen, 4-8. Juli 2016", Artikel 22 (2016).

We give combinatorial descriptions of two stochastic growth models for series-parallel networks introduced by Hosam
Mahmoud by encoding the growth process via recursive tree structures. Using decompositions of the tree structures
and applying analytic combinatorics methods allows a study of quantities in the corresponding series-parallel networks.
For both models we obtain limiting distribution results for the degree of the poles and the length of a random
source-to-sink path, and furthermore we get asymptotic results for the expected number of source-to-sink paths.

series-parallel networks, growth models, distributional analysis, source-to-sink ´paths, node degrees

http://aofa.tcs.uj.edu.pl/proceedings/aofa2016.pdf