direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments


Packet Routing: Complexity and Algorithms
Zitatschlüssel Report-003-2009
Autor Britta Peis and Martin Skutella and Andreas Wiese
Jahr 2009
Nummer 003
Monat feb
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung 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-\epsilon$ for all $\epsilon>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$.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag