Kreis- oder Wegepolytope sind die konvexen Hüllen der Inzidenzvektoren von (gerichteten) Kreisen oder Wegen in Graphen (Digraphen). Wenn man nur Kreise oder Wege bestimmter Kardinalitäten zulässt (= Anzahl der Kanten), spricht man von kardinalitätsbeschränkten Kreis- und Wegepolytopen.

Wir untersuchen in diesem Projekt die Zusammenhänge zwischen verschiedenen Kreis- und Wegepolytopen. Ziel ist ein besseres Verständnis dieser Objekte und die Entwicklung von Methoden zur Übertragung der zugehörigen Ungleichungen. Wir erhoffen uns davon Fortschritte bei der Lösung von Problemen im Zusammenhang mit Telekommunikations- und Verkehrsnetzwerken wie z.B. der Linienplanung.

• Egon Balas (Carnegy Mellon U, Pittsburgh, USA)
• Volker Kaibel (U Magdeburg)