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.
