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

On the Hardness of Finding Small Shortest Path Routing Conflicts

Zitieren Sie bitte immer diese 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.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Andreas Bley
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:computational complexity; shortest path routing
MSC-Klassifikation: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]
Datum der Erstveröffentlichung:06.05.2009
Schriftenreihe (Bandnummer):ZIB-Report (09-15)
ISSN:1438-0064
ZIB-Reportnummer:09-15
Verlagspublikation:Appeared in: Proceedings of 4th International Network Optimization Conference (INOC2009)
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.