Maximale Flüsse in fast-planaren Graphen [Elektronische Ressource] = Maximum flows in nearly planar graphs / vorgelegt von Jan Martin Hochstein

Jan Hochstein

Description

Maximale Flu¨sse infast–planaren GraphenMaximum Flows in Nearly–planar GraphsVom Fachbereich Informatikder Technischen Universit¨at DarmstadtgenehmigteInaugural-Dissertationzur Erlangung des Doktorgradesder Naturwissenschaftenvorgelegt vonDipl.-Math.Jan Martin Hochsteinaus G¨ottingenReferenten der Arbeit: Prof. Dr. Karsten WeiheProf. Dr. Michael KaufmannEinreichungsdatum : 18. Dezember 2006Pru¨fungsdatum : 21. Mai 2007Darmstadt 2007D 17iiZusammenfassungDas Maximalfluss–Problem ist eines der besterforschten Probleme in derkombinatorischen Optimierung. Gefragt ist hierbei nach dem maximalenstatischen Durchsatz durch ein Netzwerk zwischen dem Startknoten s unddem Zielknotent. Beispiele hierfu¨r sind Netzwerke aus Rohren oder Kabelnoder Strassen- und Schienennetze.Das Problem hat aber auch viele Verbindungen zu anderen Themen derkombinatorischenOptimierungundAnwendungen inso weitgestreutenGe-bieten wie CAD, Bildverarbeitung und Projektplanung.Es ist wohlbekannt, dass das Maximalfluss–Problem in planaren Graphenwesentlichschneller gel¨ost werden kann als in allgemeinenGraphen. Allerd-ings gibt es bisher keine Ergebnisse fu¨r fast–planare Graphen. Mit fast–planarbezeichnenwirGraphen, diewenigenicht–planareStellenhaben, wiezum Beispiel ein Straßennetz mit wenigen Bru¨cken und Tunneln. Dabei istes a priori nicht klar, wieviel “wenig” ist.

Sujets

• Mathematics

Informations

• Publié par: technischen_universitat_darmstadt
• Publié le: 01 janvier 2007
• Nombre de lectures: 8
• Langue: Deutsch
• Poids de l'ouvrage: 1 Mo

Extrait