BMBF Bundesministerium für Bildung und Forschung

Research-Campus MODAL

Isabel Beckenbach defends thesis at Freie Universität Berlin

Isabel Beckenbach successfully defended her Ph.D. thesis on “Matchings and Flows in Hypergraphs”. Isabel is a member of the Mathematics of Transportation and Logistics Group and working in the RailLab@Research Campus MODAL on the optimization of railway vehicle rotations for the ICE high speed trains of Deutsche Bahn. Hypergraph models are convenient to deal with constraints on train composition and regularity. An algorithmic hypergraph theory is therefore needed in order to compute trip assignments and vehicle flows through large networks. Isabel’s thesis provides pioneering results in this direction: a generalization of the fundamental theorem of Hall that characterizes the existence of perfect matchings in normal hypergraphs, a tight cut decomposition theorem for matching-covered uniformizable hypergraphs, and a purely combinatorial network simplex algorithm to compute a minimum-cost hyperflow in graph-based hypergraphs. The photo shows (from left to right) Ralf Borndörfer (head of committee), Heike Siebert (supervisor), Isabel Beckenbach, Winfried Hochstättler (reviewer), Markus Köbis (committee member).