#
Monday Lecture and Colloquium

**January 22 , 2007**

Technische Universität Berlin

Fakultät II, Institut für Mathematik

Str. des 17. Juni 136

10623 Berlin

MA 041

** Lecture - 14:15**

###
Rolf Möhring - TU Berlin

### Graph Methods: Flows over Time and Applications

*Abstract:*

Traffic management and route guidance are optimization problems by
nature. We want to utilize the available street network in such a way
that the total network “load” is minimized or the “throughput” is
maximized. This lecture deals with the mathematical aspects of such
optimization problems from the viewpoint of network flow theory.
Two important features that distinguishes them from well-known static
flows are “congestion” and “time”. “Congestion” captures the fact
that travel times increase with the amount of flow on the streets,
while “time” refers to the movement of cars along a path as a “flow
over time”. We will survey results from several mathematical flow
models that become increasingly more difficult as they capture more
and more of these two features and report on their use in applications.

**Colloquium - 16:00**

###
Paul Bonsma - TU Berlin

###
Spanning trees with many leaves: fast FPT algorithms and preprocessing on
subgraphs with low treewidth

*Abstract:*

The decision problem MaxLeaf has as input a connected graph G on n vertices,
and an integer k. The question is whether G has a spanning tree with at least
k leaves. This problem is NP-complete. When k is chosen as the parameter of
this problem, an algorithm for it is a Fixed Parameter Tractable (FPT)
algorithm if its complexity can be bounded by f(k)g(n) for some polynomial g
and arbitrary function f. The growth rate of f mainly determines the speed of
the algorithm.
We present two FPT algorithms for MaxLeaf. The first is short and simple, and
has f(k)=O(9.49^k). The second is the current fastest FPT algorithm for
MaxLeaf, with f(k)=O(8.12^k). It employs a preprocessing algorithm to reduce
certain subgraphs, which is closely related to standard methods of solving
decision problems on graphs with bounded treewidth.
In this talk, FPT algorithms and treewidth techniques will be introduced, only
basic knowledge of graph theory and computational complexity theory will be
assumed.

Letzte Aktualisierung:
16.01.2007