Schwellenverhalten zufälliger Strukturen, Fehlertoleranz und routing Algorithmen bei Kommunikationsnetzen, Heuristiken auf zufälligen Eingaben

• Antragsteller: Professor Dr. Andreas Goerdt
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 1999 bis 2006
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5184082

Das Generalthema des Projekts ist die vielfach experimentell beobachtete und oft auch mathematisch nachgewiesene Tatsache, daß typische kombinatorische Objekte ihre Struktur in Abhängigkeit von geeigneten Parametern plötzlich deutlich ändern. Man spricht in diesem Zusammenhang von Schwellenphänomenen. Strukturen an derartigen Schwellen zeigen oft ein algorithmisch besonders schwierig zu behandelndes Verhalten, das sie als Testeingaben neu entwickelter Algorithmen geeignet sein läßt. Im Sinne einer experimentellen theoretischen Informatik sollen, aufbauend auf neueren bemerkenswerten Fortschritten, bisher nur experimentell bekannte Schwellenphänomene von kombinatorischen Strukturen, Kommunikationsalgorithmen und Fehlertoleranzeigenschaften von Kommunikationsnetzen theoretisch bewiesen werden. Was die Forschung im Bereich der Algorithmen angeht, ist es das Ziel der geplanten Untersuchungen, nachzuweisen, wie Eingaben eines Algorithmus aussehen müssen, mit denen seine Effizienz überzeugend und allgemein anerkannt nachgewiesen kann.
Im Umfeld des Projekts arbeitet der Antragsteller mit Wissenschaftler der University of Toronto, Kanada, zusammen.

• DFG-Verfahren: Sachbeihilfen