Title :
Parallel Label-Setting Multi-objective Shortest Path Search
Author :
Sanders, P. ; Mandow, Lawrence
Author_Institution :
Inst. for Theor. Inf., Karlsruhe Inst. of Technol., Karlsruhe, Germany
Abstract :
We present a parallel algorithm for finding all Pareto optimal paths from a specified source in a graph. The algorithm is label-setting, i.e., it only performs work on distance labels that are optimal. The main result is that the added complexity when going from one to multiple objectives is completely parallelizable. The algorithm is based on a multiobjective generalization of a priority queue. Such a Pareto queue can be efficiently implemented for two dimensions. Surprisingly, the parallel biobjective approach yields an algorithm performing asymptotically less work than the previous sequential algorithms. We also discuss generalizations for d ≥ 3 objective functions and for single target search.
Keywords :
Pareto analysis; computational complexity; graph theory; parallel algorithms; queueing theory; Pareto optimal paths; graph source; multiobjective generalization; parallel algorithm; parallel biobjective approach; parallel label-setting multiobjective shortest path search; priority queue; sequential algorithms; single target search; Computational modeling; Data structures; Parallel algorithms; Pareto optimization; Program processors; Search problems; graph algorithm; multicriteria; shortest paths;
Conference_Titel :
Parallel & Distributed Processing (IPDPS), 2013 IEEE 27th International Symposium on
Conference_Location :
Boston, MA
Print_ISBN :
978-1-4673-6066-1
DOI :
10.1109/IPDPS.2013.89