Parallel Algorithms for Graph Optimization using Tree Decompositions

Sullivan, Blair D¹  Weerapurage, Dinesh P¹  Groer, Christopher S¹ 

[1] ORNL

关键词: ALGORITHMS;    DYNAMIC PROGRAMMING;    EXACT SOLUTIONS;    IMPLEMENTATION;    OPTIMIZATION;    POLYNOMIALS tree decomposition;    MADNESS;    HPC;    parallel;    dynamic programming;    graph;    graph theory;    weighted independent set;   

DOI  :  10.2172/1042920
RP-ID  :  ORNL/TM-2012/194
PID  :  OSTI ID: 1042920
Others  :  Other: KJ0401000
Others  :  ERKJU04
Others  :  TRN: US201213%%209

学科分类：社会科学、人文和艺术（综合）

美国|英语

来源: SciTech Connect

【 摘 要 】

Although many $\cal{NP}$-hard graph optimization problems can be solved in polynomial time on graphs of bounded tree-width, the adoption of these techniques into mainstream scientific computation has been limited due to the high memory requirements of the necessary dynamic programming tables and excessive runtimes of sequential implementations. This work addresses both challenges by proposing a set of new parallel algorithms for all steps of a tree decomposition-based approach to solve the maximum weighted independent set problem. A hybrid OpenMP/MPI implementation includes a highly scalable parallel dynamic programming algorithm leveraging the MADNESS task-based runtime, and computational results demonstrate scaling. This work enables a significant expansion of the scale of graphs on which exact solutions to maximum weighted independent set can be obtained, and forms a framework for solving additional graph optimization problems with similar techniques.