Kreise in großen Graphen

• Antragsteller: Professor Dr. Peter Gritzmann
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2001 bis 2006
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5322852

Bei der Untersuchung komplexer Netzwerke treten Probleme auf, die sich mit graphentheoretischen Methoden behandeln lassen. Dabei besteht Bedarf an effizienten Algorithmen, die speziell auf große Datenmengen zugeschnitten sind. In den ersten beiden Jahren des Projektes soll ein Problem der Schaltkreisanalyse großer elektrischer Netzwerke im Vordergrund stehen. Es ergibt sich bei der Lösung der sogenannten Netzwerkgleichung für reale Schaltkreise. Die numerische Integration des entsprechenden Differentialgleichungssystems kann durch Konstruktion einer minimalen Kreisbasis des zugrundeliegenden Graphen erheblich beschleunigt werden. Ansatz zur Entwicklung von Algorithmen bildet die Analyse und Ausnutzung spezieller Struktureigenschaften der zugrundeliegenden realen elektrischen Schaltkreise. Die zu entwickelnden Methoden sollen für Netzwerke mit Größenordnungen von bis zu 10(hoch)6 Knoten und 10(hoch)8 Kanten effizient anwendbar sein. (Die Datensätze stammen von der Firma Infineon Technologies AG.) In einer späteren Projektphase sollen die gefundenen Ergebnisse und die gewonnenen Erfahrungen auf weitere praktische Probleme der Elektrotechnik angewandt werden. Hierzu gehören insbesondere Fragen der Kreisüberdeckung von Graphen, die große optische Netzwerke modellieren.

• DFG-Verfahren: Schwerpunktprogramme
• Teilprojekt zu: SPP 1126: Algorithmik großer und komplexer Netzwerke