Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

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

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

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