Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14429
For citation please use:
Main Title: Logarithmic inapproximability results for the minimum shortest path routing conflict problem
Author(s): Bley, Andreas
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15656
http://dx.doi.org/10.14279/depositonce-14429
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: Nowadays most data networks use shortest path protocols such as OSPF or IS-IS to route traffic. Given administrative routing lengths for the links of a network, all data packets are sent along shortest paths with respect to these lengths from their source to their destination. One of the most fundamental problems in planning shortest path networks is to decide whether a given set S of routing paths forms a valid routing and, if this is not the case, to find a small subset R of paths that cannot occur together in any valid routing. In this paper we show that it is NP-hard to approximate the minimal size or the minimal weight of a shortest path conflict $R\subseteq S$ by a factor less than $c\log |S|$ for some $c>0$.
Subject(s): shortest path routing
computational complexity
Issue Date: 1-Jul-2009
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
MSC 2000: 90C60 Abstract computational complexity for mathematical programming problems
90B18 Communication networks
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 2009, 25
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-025-2009.pdf
Format: Adobe PDF | Size: 160.79 kB
DownloadShow Preview
Thumbnail

Item Export Bar

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