Journal
IEEE 27TH INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM (IPDPS 2013)
Volume -, Issue -, Pages 215-224Publisher
IEEE COMPUTER SOC
DOI: 10.1109/IPDPS.2013.89
Keywords
-
Categories
Funding
- DFG [SA 933/5-2, SA 933/3-3]
- Consejerya de Innovacion, Ciencia y Empresa, Junta de Andalucya (Espana) [P07-TIC-03018]
- Spanish Government, Plan Nacional de I+D+i [TIN2009-14179]
Ask authors/readers for more resources
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 multi-objective 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available