Bachelorseminar Network Flows

Aktuelles

Inhalte

Everywhere we look in our daily lives, networks are apparent: e.g.

• Electrical and powernetworks
• Telephone networks
• National highway systems,
• Rail networks,
• Manufacturing and distribution networks,
• computer networks.

In all of these problem domains, and in many more, we wish to move some entity (electricity, a consumer product, a person or a vehicle, a message) from one point to another in an underlying network, and to do so as efficiently as possible, both to provide good service to the users of the network and to use the underlying (and typically expensive) transmission facilities effectively.

We consider the following problem areas:

• Maximum flow problem. If a network has capacities on arc flows, how can we send as much flow as possible between two points in the network while honoring the arc flow capacities?
• Minimum cost flow problem. If we incur a cost per unit flow on a network with arc capacities and we need to send units of a good that reside at one or more points in the network to one or more other points, how can we send the material at minimum possible cost?
• Assignment and Matching

  A Matching in a graph G = (N, A) is a set of arcs with the property that every node is incident to at most one arc in the set; thus a matching induces a pairing of (some of) the nodes in the graph using the arcs in A. The matching problem seeks a matching that optimizes some criteria.

  Matching problems on a bipartite graphs (i.e., those with two sets of nodes and with arcs that join only nodes between the two sets, as in the assignment and transportation problems) are called bipartite matching problems, There are two additional ways of categorizing matching problems: cardinality matching problems, which maximize the number of pairs of nodes matched, and weighted matching problems, which maximize or minimize the weight of the matching.

  The weighted matching problem on a bipartite graph is also known as the assignment problem.

• Multicommodity flow problem. Multicommodity flow problems arise when several commodities use the same underlying network

Ablauf

Alle Studierenden erhalten ein konkretes Thema. Sie erhalten nach Zuteilung eines Platzes im Seminar eine Themenliste und können hier Wünsche äußern, die im Abgleich mit den anderen Studenten berücksichtigt werden. 

Sie werden in Ihrem Thema und Ihrer Ausarbeitung individuell betreut.

Themen

Nach Zuteilung der Seminarplätze erhalten Sie weitere Informationen zu den Themen per E-Mail, sodass Sie ihre Auswahl besser treffen können.

Sprache

Vortrag und Ausarbeitung können auf deutsch oder englisch sein.

Termine

Das Seminar findet in 3 bis 4 Blöcken statt, immer Mittwochs, 14-18 Uhr, Oettingenstr. 67, C 003.

• 24.10.2018: Vorbesprechung und Themenvergabe

Personen

• Leitung: Prof. Dr. Mila Majster-Cederbaum
• Administrative Verwaltung: Dr. Philipp Wendler
  

Materialien

Hörerkreis

Bachelor Informatik oder Medieninformatik. Gefordert ist ein Vortrag von 40 Minuten mit anschließender, 10 minütiger, Diskussion und eine Ausarbeitung mit 7-12 Seiten.

Benötigte Vorkenntnisse

Vorlesung “Algorithmen und Datenstrukturen”