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

An Improved Multiobjective Shortest Path Algorithm

Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-79712
  • We present a new label-setting algorithm for the Multiobjective Shortest Path (MOSP) problem that computes the minimal complete set of efficient paths for a given instance. The size of the priority queue used in the algorithm is bounded by the number of nodes in the input graph and extracted labels are guaranteed to be efficient. These properties allow us to give a tight output-sensitive running time bound for the new algorithm that can almost be expressed in terms of the running time of Dijkstra's algorithm for the Shortest Path problem. Hence, we suggest to call the algorithm \emph{Multiobjective Dijkstra Algorithm} (MDA). The simplified label management in the MDA allows us to parallelize some subroutines. In our computational experiments, we compare the MDA and the classical label-setting MOSP algorithm by Martins', which we improved using new data structures and pruning techniques. On average, the MDA is $\times2$ to $\times9$ times faster on all used graph types. On some instances the speedup reaches an order of magnitude.

Volltext Dateien herunterladen

Metadaten exportieren

Metadaten
Verfasserangaben:Pedro Maristany de las CasasORCiD, Antonio Sedeno-NodaORCiD, Ralf BorndörferORCiD
Dokumentart:ZIB-Report
Freies Schlagwort / Tag:Multiobjective Shortest Path Problem; Network Optimization; Output-Sensitive Multiobjective Combinatorial Problems
MSC-Klassifikation:05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C85 Graph algorithms [See also 68R10, 68W05]
68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Rxx Discrete mathematics in relation to computer science / 68R10 Graph theory (including graph drawing) [See also 05Cxx, 90B10, 90B35, 90C35]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90-02 Research exposition (monographs, survey articles)
CCS-Klassifikation:G. Mathematics of Computing / G.2 DISCRETE MATHEMATICS
Datum der Erstveröffentlichung:18.06.2021
Schriftenreihe (Bandnummer):ZIB-Report (20-26)
ISSN:1438-0064
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.