TY - GEN A1 - Bley, Andreas T1 - On the Hardness of Finding Small Shortest Path Routing Conflicts N2 - 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. T3 - ZIB-Report - 09-15 KW - shortest path routing KW - computational complexity Y1 - 2009 UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/1127 UR - https://nbn-resolving.org/urn:nbn:de:0297-zib-11276 SN - 1438-0064 ER -