On the <I>k</I>-splittable Flow Problem
| dc.contributor.author | Baier, Georg | |
| dc.contributor.author | Köhler, Ekkehard | |
| dc.contributor.author | Skutella, Martin | |
| dc.date.accessioned | 2021-12-17T10:18:18Z | |
| dc.date.available | 2021-12-17T10:18:18Z | |
| dc.date.issued | 2002 | |
| dc.description.abstract | In traditional multi-commodity flow theory, the task is to send a certain amount of each commodity from its start to its target node, subject to capacity constraints on the edges. However, no restriction is imposed on the number of paths used for delivering each commodity; it is thus feasible to spread the flow over a large number of different paths. Motivated by routing problems arising in real-life applications, such as, e.g., telecommunication, unsplittable flows have moved into the focus of research. Here, the demand of each commodity may not be split but has to be sent along a single path. | en |
| dc.identifier.issn | 2197-8085 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15969 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14742 | |
| 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 | graph algorithms | en |
| dc.subject.other | network flow | en |
| dc.subject.other | routing | en |
| dc.title | On the <I>k</I>-splittable 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, 739 | 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 |