Project Details
Projekt
Effiziente Algorithmen für wegbasierte und dynamische Flussprobleme in großen Netzwerken
Subject Area
Theoretical Computer Science
Term
from 2001 to 2007
Project identifier
Deutsche Forschungsgemeinschaft (DFG) - Project number 5322708
Effiziente Algorithmen für Flussprobleme sind von entscheidender Bedeutung für eine Vielzahl netzbasierter Anwendungen, etwa bei der Verkehrsführung und -planung, der Telekommunikation und dem Datenverkehr im Internet. Wichtiges Leitthema solcher Anwendungen ist - im weitesten Sinne - die Minimierung der Netzbelastung bei (weitgehender) Erfüllung aller vorhandenen Nutzerwünsche. Diese Thematik führt zu Optimierungsproblemen in Netzen, die bisher meist traditionell mit Standardverfahren der Netzwerkoptimierung behandelt werden. Diese Verfahren lassen jedoch wesentliche Aspekte außer Acht, die gerade in komplexen und großen Netzen von Bedeutung sind: Netze sind i.a. nur noch implizit gegeben und beliebige Flussführungen sind nicht mehr zulässig. In diesem Projekt sollen Algorithmen zur Behandlung solcher "wegbasierter" Fluss- bzw. Mehrgüterflussprobleme entwickelt und erprobt werden. Hierzu muss insbesondere in theoretischer Hinsicht Neuland betreten werden, da zugleich neue, aus der Wegbasierung resultierende Nebenbedingungen und die Forderung nach Effizienz auf großen Netzen berücksichtigt werden müssen. In praktischer Hinsicht bilden Fragen der optimalen Verkehrsführung den Anwendungshintergrund, wobei hierfür auch große Netze als Praxisdaten zur Verfügung stehen.
DFG Programme
Priority Programmes
Subproject of
SPP 1126:
Algorithmics of Large and Complex Networks
