DocumentCode :
625590
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
fYear :
2013
fDate :
20-24 May 2013
Firstpage :
215
Lastpage :
224
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel & Distributed Processing (IPDPS), 2013 IEEE 27th International Symposium on
Conference_Location :
Boston, MA
ISSN :
1530-2075
Print_ISBN :
978-1-4673-6066-1
Type :
conf
DOI :
10.1109/IPDPS.2013.89
Filename :
6569813
Link To Document :
بازگشت