Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14448
For citation please use:
Main Title: Packet Routing: Complexity and Algorithms
Author(s): Peis, Britta
Skutella, Martin
Wiese, Andreas
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15675
http://dx.doi.org/10.14279/depositonce-14448
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: Routing of packets is one of the most fundamental tasks in a network. Limited bandwith requires that some packets cannot move to their destination directly but need to wait in intermediate nodes on their path or take detours. It is desirable to find schedules that ensure fast delivery of the packets, in particular for time critial applications. In this paper we investigate the packet routing problem theoretically. We prove that the problem cannot be approximated with a factor of 6/5-ε for all ε>0 unless P=NP. We show that restricting the graph topology to planar graphs or trees still does not allow a PTAS. For trees we give 2-approximation algorithms for the directed and the undirected case. If the lengths of the paths of the packets are pairwise different, we can compute a schedule of length D on directed trees. Finally, we show that it is NP-hard to approximate the packet routing problem with an absolute error of k for any k>=0.
Subject(s): packet routing
complexity
NP-hardness
approximation algorithms
store-and-forward packet routing
Issue Date: 2009
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2009, 03
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Report-003-2009.pdf
Format: Adobe PDF | Size: 514.25 kB
DownloadShow Preview
Thumbnail

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.