Cycles in large graphs

• Applicant: Professor Dr. Peter Gritzmann
• Subject Area: Theoretical Computer Science
• Term: from 2001 to 2006
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Priority Programmes
• Subproject of: SPP 1126: Algorithmics of Large and Complex Networks