Maximale Flüsse in fast-planaren Graphen [Elektronische Ressource] = Maximum flows in nearly planar graphs / vorgelegt von Jan Martin Hochstein
122 pages
Deutsch
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

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

-

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
122 pages
Deutsch

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

Informations

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

Exrait

  • Accueil Accueil
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • BD BD
  • Documents Documents