SPP 731:  Effiziente Algorithmen für diskrete Probleme und ihre Anwendungen

• Subject Area: Computer Science, Systems and Electrical Engineering
• Term: from 1995 to 2000
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5465944

The strategic goal of this research cluster that ended in the year 2000 was to direct the basic research in computer science and discrete mathematics that has led to interesting new methods in the past towards applications in science and technology. In line with this goal, projects funded within the research cluster aimed at extending the basic research on algorithms from previous years and decades towards specific applications inside and - especially - outside computer science.The projects investigated problems that arise directly from applications, whose domains include, e.g., circuit design, computer-aided design in construction and manufacturing, traffic, robotics, chemistry, and biology. The problems investigated have a direct relevance to their respective applications. In many cases, this relevance to the application is substantiated by cooperation or contacts with researchers from the application discipline.Solution methods are based on recent developments on discrete algorithms. Algorithmic research that is relevant here includes data structures, graph algorithms, computational geometry, computer algebra and symbolic computation, combinatorial optimization, randomised algorithms, parallel and distributed algorithms and pattern matching. The research in the cluster extended the solution methods rather than merely applying them.Solution methods were validated through a mixture of experimentation on real-life data stemming from the application and theoretical analysis.

• DFG Programme: Priority Programmes
• International Connection: Austria

Projects

• Algorithmen zur Konstruktion, Klassifikation und Visualisierung hochgeordneter räumlicher Strukturen (Applicant Dress, Andreas )
• Algorithmen über omega-Automaten und Anwendungen in der Programmkonstruktion und -verifikation (Applicant Thomas, Wolfgang )
• CAD-gerechte Oberflächen- und Volumenrekonstruktion komplexer Objekte aus einer Menge von unstrukturierten Oberflächenpunkten (Applicant Brunnett, Guido )
• Design, Analyse, Implementierung, Evaluierung und experimentelle Anwendung von Algorithmen zum Zeichnen von Graphen (Applicant Mutzel, Petra )
• Design, Analyse, Implementierung, Evaluierung und experimentelle Anwendung von Algorithmen zum Zeichnen von Graphen (Applicant Jünger, Michael )
• Design, Analyse, Implementierung, Evaluierung und experimentelle Anwendung von Algorithmen zum Zeichnen von Graphen (Applicant Näher, Stefan )
• Design, Analyse, Implementierung und experimentelle Anwendungen von Algorithmen zum Zeichnen von Graphen (Applicant Brandenburg, Franz Josef )
• Dimensionierung analoger Schaltkreise mit Methoden der Computeralgebra (Applicant Greuel, Gert-Martin )
• Effiziente Algorithmen für diskrete und diskretisierte Standortprobleme (Applicant Hamacher, Horst W. )
• Effiziente Algorithmen zur formalen Verifikation von VLSI-Designs (Applicant Prömel, Hans Jürgen )
• Effiziente Algorithmen zur Logiksynthese und Verifikation bei VLSI-Schaltkreisen (Applicant Becker, Bernd )
• Effiziente diskrete Algorithmen zur Flächenrückführung und Flächeneinpassung (Applicant Müller, Heinrich )
• Entwicklung, Analyse und experimentelle Erprobung von kompetitiven Algorithmen für die Bahnplanung autonomer Systeme (Applicant Klein, Rolf )
• Entwicklung effizienter Algorithmen für die Minimierung von Arbeiterlaufzeiten in Flow-Shop-Fertigungssystemen (Applicant Wanke, Egon )
• Entwicklung effizienter algorithmischer Verfahren zur Lösung des zweidimensionalen Plazierungsproblems (sog. Nesting-Problem) unter Berücksichtigung der in der textilverarbeitenden Industrie auftretenden Randbedingungen (Applicant Lengauer, Thomas )
• Entwicklung und Implementierung von effizienten parallelen Algorithmen für Molekulardynamik-Simulationen von synthetischen Polymeren (Applicant Lenhof, Hans-Peter )
• Entwicklung von Algorithmen für den Vergleich und die Rekonstruktion der evolutionären Zusammenhänge von Gen- und Genomsequenzen (Applicant Vingron, Martin )
• Entwurf von Analyse von BDD-basierten Datenstrukturen zur Repräsentation und automatischen Bearbeitung sequentieller Schaltkreise und Systeme (Applicant Meinel, Christoph )
• Erzeugung von effizientem Ableitungscode durch Knotenelimination im Berechnungsgraphen (Applicant Griewank, Andreas )
• Gekoppelte Auswertealgorithmen zur molekularen Strukturerkennung mit GC/MS (Applicant Döhler, Hermann )
• Gekoppelte Auswertealgorithmen zur molekularen Strukturerkennung mit GC/MS (Applicant Kerber, Adalbert )
• Graphalgorithmen zur Optimierung von Sendernetzen (Applicant Lautemann, Clemens )
• Hierarchische Realzeitalgorithmen: Grundlagen und Walk-trough-Animation (Applicant Meyer auf der Heide, Friedhelm )
• Kombinatorische Algorithmen zur Vierecks- und Hexaedernetzgenerierung für Finite-Elemente-Verfahren (Applicant Möhring, Rolf H. )
• Kombinatorische Idealisierung des Problems der Proteinfaltung und deren Lösung durch effiziente Algorithmen nach dem Greedy-Prinzip (Applicant Lengauer, Thomas )
• Lokalisation und Navigation für reale autonome Roboter in Produktions- und Serviceumgebungen mittels Laserradar (Applicant Noltemeier, Hartmut )
• Modellierung paralleler Prozesse mittels algebraischer Methoden (Applicant Mayr, Ernst W. )
• Partitionierungsalgorithmen für Modelldatenstrukturen zur parallelen compilergesteuerten Logiksimulation (Applicant Rünger, Gudula )
• Praktikable Algorithmen für Datentransport und andere Basisprobleme auf skalierbaren Architekturen (Applicant Kunde, Manfred )
• Reduktion der Teilevielfalt auf der Basis einer geometrisch orientierten Ähnlichkeitssuche (Applicant Kriegel, Hans-Peter )
• Robuste Algorithmen zur Auswertung, Rekonstruktion und Visualisierung von graphenbasierten Verkehrsdaten (Applicant Wagner, Dorothea )
• Sequentielle und verteilte Algorithmen zur selektiven Auswertung von Min/Max-Bäumen (Applicant Monien, Burkhard )
• Skalierbare Algorithmen für die parallele Bewegungsplanung in dynamischen Umgebungen (Applicant Wörn, Heinz )
• Vektororientierte und hybride Verschneidungsalgorithmen für Geoinformationssysteme (Applicant Hinrichs, Klaus H. )

• Spokesperson: Professor Dr. Thomas Lengauer