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

• Applicant: Professor Dr. Andreas Goerdt
• Subject Area: Theoretical Computer Science
• Term: from 1999 to 2006
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Research Grants