The Quickest Multicommodity Flow Problem
| dc.contributor.author | Fleischer, Lisa | |
| dc.contributor.author | Skutella, Martin | |
| dc.date.accessioned | 2021-12-17T10:05:18Z | |
| dc.date.available | 2021-12-17T10:05:18Z | |
| dc.date.issued | 2002 | |
| dc.description.abstract | 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. | en |
| dc.identifier.issn | 2197-8085 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15471 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14244 | |
| dc.language.iso | en | en |
| dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |
| dc.subject.ddc | 510 Mathematik | en |
| dc.subject.other | approximation algorithms | en |
| dc.subject.other | dynamic flow | en |
| dc.subject.other | flow over time | en |
| dc.subject.other | graph algorithms | en |
| dc.subject.other | network flow | en |
| dc.subject.other | routing | en |
| dc.title | The Quickest Multicommodity Flow Problem | en |
| dc.type | Research Paper | en |
| dc.type.version | submittedVersion | en |
| tub.accessrights.dnb | free | en |
| tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik | de |
| tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |
| tub.affiliation.institute | Inst. Mathematik | de |
| tub.publisher.universityorinstitution | Technische Universität Berlin | en |
| tub.series.issuenumber | 2002, 728 | en |
| tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |
| tub.subject.msc2000 | 90C27 Combinatorial optimization | en |
| tub.subject.msc2000 | 90B10 Network models, deterministic | en |
| tub.subject.msc2000 | 90C35 Programming involving graphs or networks | en |
| tub.subject.msc2000 | 05C38 Paths and cycles | en |
| tub.subject.msc2000 | 05C85 Graph algorithms | en |
| tub.subject.msc2000 | 90C59 Approximation methods and heuristics | en |
| tub.subject.msc2000 | 68W25 Approximation algorithms | en |
| tub.subject.msc2000 | 68Q25 Analysis of algorithms and problem complexity | en |