direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Preprints 2009

Packet Routing on the Grid
Zitatschlüssel Report-012-2009
Autor Britta Peis and Martin Skutella and Andreas Wiese
Jahr 2009
Nummer 012
Monat mar
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung The packet routing problem, i.e., the problem to send a given set of unit-size packets through a network on time, belongs to one of the most fundamental routing problems with important practical applications, e.g., in traffic routing, parallel computing, and the design of communication protocols. The problem involves critical routing and scheduling decisions. One has to determine a suitable (short) origin-destination path for each packet and resolve occurring conflicts between packets whose paths have an edge in common. The overall aim is to find a schedule with minimum makespan. A significant topology for practical applications are grid graphs. In this paper, we therefore investigate the packet routing problem under the restriction that the underlying graph is a grid. We establish approximation algorithms and complexity results for the general problem on grids, and under various constraints on the start and destination vertices or on the paths of the packets.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag