Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

On the Hardness of Finding Small Shortest Path Routing Conflicts

  • 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.

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Andreas Bley
Document Type:In Proceedings
Parent Title (English):Proceedings of 4th International Network Optimization Conference (INOC2009)
Year of first publication:2009
Preprint:urn:nbn:de:0297-zib-11276
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.