Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14440
For citation please use:
Main Title: Packet Routing on the Grid
Author(s): Peis, Britta
Skutella, Martin
Wiese, Andreas
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15667
http://dx.doi.org/10.14279/depositonce-14440
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: 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.
Subject(s): packet routing
grid graphs
complexity
NP-hardness
approximation algorithms
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, 12
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-012-2009.pdf
Format: Adobe PDF | Size: 634 kB
DownloadShow Preview
Thumbnail

Item Export Bar

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