An der Universität Salzburg wurde ein offenes Problem aus den 1970er Jahren gelöst: Die Entwicklung eines schnellen Algorithmus zur Berechnung der Konnektivität von Netzwerken. Sie ist ein Maß für die Robustheit eines Netzwerks und gibt an, ab welcher Anzahl von ausgefallenen Netzwerkteilnehmern das Netzwerk nicht mehr verbunden ist.
Am Fachbereich Computerwissenschaften der Universität Salzburg wurden in den letzten Jahren die schnellsten derzeit bekannten Algorithmen für eine Reihe von Rechenproblemen entwickelt.
Aktuell ist dem Jungforscher, Professor Sebastian Forster, und seiner Kollegin, Liu Yang, von der Universität Yale ein Durchbruch in der Berechnung der Konnektivität eines Netzwerks gelungen. Die Konnektivität gibt an, ab welcher Anzahl von ausgefallenen Netzwerkteilnehmern das Netzwerk nicht mehr verbunden ist. Sie ist also ein Maß der Robustheit eines Netzwerks.
Die Berechnung der Konnektivität ist ein klassisches Problem der theoretischen Informatik, das nicht nur fundamentale mathematische Bedeutung hat, sondern auch in der Praxis relevant ist.
Exemplarisch sei hier das Straßennetz einer Stadt genannt: Wie viele Kreuzungen müssen mindestens frei passierbar sein, um den Verkehrsfluss der Stadt zu gewährleisten? Oder anders gefragt: Ab wie vielen verstopften Kreuzungen bricht der Verkehr zusammen und die Erreichbarkeit von A nach B ist nicht mehr möglich?
Trotz einiger vielversprechender Ansätze in den 1990er Jahren war die Frage, der schnellen Berechnung dieser Maßzahl, seit den 1970er Jahren ungelöst.
Anfang Jänner werden die beiden Forschenden mit Kollegen aus Schweden, die fast zeitgleich zu einer ähnlichen Lösung des Problems gelangten, ihre Ergebnisse auf der wichtigsten internationalen Konferenz für Algorithmen, dem „Symposium on Discrete Algorithms“, vorstellen.
