Cycles in large graphs

点击翻译按钮获取中文摘要

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.