Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • Treffer 9 von 30
Zurück zur Trefferliste

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.

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Andreas Bley
Dokumentart:Konferenzbeitrag
Titel des übergeordneten Werkes (Englisch):Proceedings of 4th International Network Optimization Conference (INOC2009)
Jahr der Erstveröffentlichung: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.