Connectivity Problems of Networks: Structures and Algorithms

April 1-12, 2001

Location: Institut für Informatik, Freie Universität Berlin
Takustr. 9, D-14195 Berlin (Dahlem), Room 005

CONTENTS: By a connectivity problem of networks we mean one concerning paths, flows, circuits, trees, cuts, arborescences, etc. Although a great majority of problems in the area is NP-complete there are several fundamental problems which are tractable. Maximum flows or shortest paths are two well-known basic examples of such problems. We will concentrate on topics which cannot be handled by classical network flow techniques and need new approaches. Examples are: disjoint arborescences, edge-disjoint paths in planar graphs, Nash-Williams' orientation result, splitting theorems, the Nagamochi-Ibaraki algorithm, optimal connectivity augmentation, connectivity orientation problems. Our goal is to provide a comprehensive map of tractable problems of the area and to explain basic methods and approaches. Special emphasis will be put on exploring the background and on algorithmic aspects. During the morning sessions the theoretical material will be exhibited and discussed, while in the afternoon "exercise" sessions challenging exercises and problems will provide participants an opportunity to test and improve their problem-solving ability in order to obtain sufficient familiarity with the theory.

PREREQUISITES: Basic knowledge in graph theory, matroid theory, and linear programming.

LECTURERS: Prof. András Frank, Tibor Jordan, Eötvös Loránd University Budapest