Kurze Kreise durch vorgeschriebene Knoten eines Graphen
| Talking persons: |
| Dr. Frank Göring |
| Abstract: |
| In einem gegebenen Graphen G suchen wir zu einer gegebenen Teilmenge T seiner Knoten möglichst kurze Kreise, die diese Teilmenge überdecken. Damit überhaupt Kreise diese Teilmenge überdecken, fordern wir hinreichend hohen Zusammenhang. Wie lang kann dann ein kürzester überdeckender Kreis werden? Es wird eine scharfe Schranke in Abhängigkeit von der Knotenzahl und dem Zusammenhang des Graphen für bis zu dreielementiges T hergeleitet. Dabei wird ein Verfahren basierend auf Menger's Theorem demonstriert, um in Graphen mit gewissen Zusammenhangseigenschaften unvermeidbare Unterstrukturen aufzufinden. Eine rechentechnische Implementation des Verfahrens steht noch aus, wäre aber wünschenswert. Der Vortrag basiert auf einer gemeinsamen Arbeit mit Zsolt Tuza, Jochen Harant und Erhard Hexel. |
| Times: |
| Wednesday 4th June 2003, 9.15 am, room 1/368 |
