Packet routing on the grid

Britta Peis, Martin Skutella, Andreas Wiese

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

7 Scopus citations


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) origindestination path for each packet and resolve occurring conflicts between packets whose paths have an edge in common. The overall aim is to find a path for each packet and a routing 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.

Original languageEnglish
Title of host publicationLATIN 2010
Subtitle of host publicationTheoretical Informatics - 9th Latin American Symposium, Proceedings
Number of pages11
StatePublished - 2010
Externally publishedYes
Event9th Latin American Theoretical Informatics Symposium, LATIN 2010 - Oaxaca, Mexico
Duration: 19 Apr 201023 Apr 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6034 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference9th Latin American Theoretical Informatics Symposium, LATIN 2010


Dive into the research topics of 'Packet routing on the grid'. Together they form a unique fingerprint.

Cite this