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
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
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.