[Zurück]

M. Zeiner, U. Schmid, U. Schilcher, C. Bettstetter:
"FWF-Proposal SPRG: Structural Properties of Random Graphs";
Bericht für Institut für Technische Informatik, TU Wien; 2016.

The proposal Structural Properties of Random Graphs (SPRG) is devoted to the analysis of global properties of random graphs, like the existence of strongly connected components or a spanning tree. Particular challenges arise from our strive to consider random graph models that match real networks reasonably well, which adds various forms of time-evolution to the picture: In the case of wireless networks, for example, the graph topology may change both deterministically, due to node mobility and external interference, as well as stochastically due to fading and failures. The proposed project involves both (i) the development of suitable mathematical analysis techniques for graph structures of interest, which will primarily be based on probabilistic analysis, analytic combinatorics and similar methods, and (ii) the development of a mathematically tractable but reasonably realistic random graph models, e.g., based on directed geometric graphs, non-homogeneous point processes and similar ideas, as well as their simulation-based and analytic evaluation.

Random graphs, structural graph properties, time-evolving networks, probabilistic analysis, analytic combinatorics, simulations