Approximability of 3- and 4-hop bounded disjoint paths problems
| dc.contributor.author | Bley, Andreas | |
| dc.contributor.author | Neto, Jose | |
| dc.date.accessioned | 2021-12-17T10:08:16Z | |
| dc.date.available | 2021-12-17T10:08:16Z | |
| dc.date.issued | 2009 | |
| dc.description.abstract | A path is said to be l-bounded if it contains at most l edges. We consider two types of l-bounded disjoint paths problems. In the maximum edge- or node-disjoint path problems MEDP(l) and MNDP(l), the task is to find the maximum number of edge- or node-disjoint l-bounded (s,t)-paths in a given graph G with source s and sink t, respectively. In the weighted edge- or node-disjoint path problems WEDP(l) and WNDP(l), we are also given an integer k and non-negative edge weights, and seek for a minimum weight subgraph of G that contains k edge- or node-disjoint l-bounded (s,t)-paths. Both problems are of great practical relevance in the planning of fault-tolerant communication networks, for example. | en |
| dc.identifier.issn | 2197-8085 | |
| dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15657 | |
| dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14430 | |
| 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 | graph algorithms | en |
| dc.subject.other | length-bounded paths | en |
| dc.subject.other | complexity | en |
| dc.subject.other | approximation algorithms | en |
| dc.title | Approximability of 3- and 4-hop bounded disjoint paths problems | 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 | 2009, 24 | en |
| tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |
Files
Original bundle
1 - 1 of 1