Repository: DepositOnce â€“ institutional repository for research data and publications of TU Berlin https://depositonce.tu-berlin.de
TY - RPRT
AU - Fleischer, Lisa
AU - Skutella, Martin
PY - 2002
TI - The Quickest Multicommodity Flow Problem
DO - 10.14279/depositonce-14244
UR - http://dx.doi.org/10.14279/depositonce-14244
PB - Technische UniversitÃ¤t Berlin
LA - en
AB - 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.
KW - approximation algorithms
KW - dynamic flow
KW - flow over time
KW - graph algorithms
KW - network flow
KW - routing
ER -