• search hit 1 of 18
Back to Result List

On the Hardness of Finding Small Shortest Path Routing Conflicts

Please always quote using this URN: urn:nbn:de:0297-zib-11276
  • 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 of routing paths forms a valid routing and, if this is not the case, to find a small subset of the given paths that cannot be shortest paths simultaneously for any routing lengths. In this paper we show that it is NP-hard to approximate the size of the smallest shortest path conflict by a factor less than 7/6.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Andreas Bley
Document Type:ZIB-Report
Tag:computational complexity; shortest path routing
MSC-Classification:68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Qxx Theory of computing / 68Q25 Analysis of algorithms and problem complexity [See also 68W40]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B18 Communication networks [See also 68M10, 94A05]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C60 Abstract computational complexity for mathematical programming problems [See also 68Q25]
Date of first Publication:2009/05/06
Series (Serial Number):ZIB-Report (09-15)
ISSN:1438-0064
Published in:Appeared in: Proceedings of 4th International Network Optimization Conference (INOC2009)