[Logo Theoretical Computer Science][Go to the page of the University of Mannheim]

Research

Algorithmische Behandlung schwerer Optimierungsprobleme in Netzwerken

DFG-Sachbeihilfe Kr 1521/6-1 im Rahmen des DFG-Schwerpunktes Nr. 1126: Algorithmik großer und komplexer Netzwerke

Projektbeschreibung:

Ein zentrales Problem in Netzwerken besteht darin, (kostengünstige) Verbindungsstrukturen zu finden, die gewisse Kriterien erfüllen. Der Kern dieses Problems wird durch das Steiner-Problem in Netzwerken modelliert, also das Problem, eine gegebene Menge von Knoten in einem gewichteten Graphen möglichst kostengünstig zu verbinden. Aufbauend auf der erfolgreichen Arbeit über das Steiner-Problem werden in dem Projekt folgende Ziele verfolgt:
  1. Vertiefung des strukturellen Wissens über das Steiner-Problem, seine Relaxationen und die damit verbundenen Bearbeitungsmethoden,
  2. Anpassung und Anwendung der bereits entwickelten Algorithmen auf Fragestellungen, die sich als (Varianten von) Steiner-Problem in großen Netzwerken modellieren lassen, z.B. das aus der Biologie stammende Problem der Phylogenie,
  3. Übertragung der beim Steiner-Problem erfolgreichen Methoden auf verwandte schwere Optimierungsprobleme, insbesondere die durch ihre Netzwerkanwendungen motivierten Mehrkriterienprobleme wie gradbeschränkte Steiner- und Spannbäume.

Publikationen

[Information about the chair] [Teaching Information] [Research Information] [Information about the People of this chair] [Send a Mail]
[This Document is valid XHTML 1.0!] [This Document uses valid CSS!] [Level Double-A conformance icon, W3C-WAI Web Content Accessibility Guidelines 1.0] [c't-check of WCAG onformance icon, W3C-WAI Web Content Accessibility Guidelines 1.0]