Fleischer, LisaSkutella, Martin2021-12-172021-12-1720022197-8085https://depositonce.tu-berlin.de/handle/11303/15471http://dx.doi.org/10.14279/depositonce-14244Traditionally, 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.en510 Mathematikapproximation algorithmsdynamic flowflow over timegraph algorithmsnetwork flowroutingResearch Paper