Thumbnail Image

The Quickest Multicommodity Flow Problem

Fleischer, Lisa; Skutella, Martin

Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin

Traditionally, flows over time are solved in time expanded networks which contain one copy of the original network for each discrete time step. While this method makes available the whole algorithmic toolbox developed for static flows, its main and often fatal drawback is the enormous size of the time expanded network. In particular, this approach usually does not lead to efficient algorithms with running time polynomial in the input size since the size of the time expanded network is only pseudo-polynomial.