Parallel Algorithms for Graph Optimization using Tree Decompositions

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

Oak Ridge National Laboratory

关键词: Graph Theory;    Tree Decomposition;    Dynamic Programming;    Polynomials Tree Decomposition;    99 General And Miscellaneous//Mathematics, Computing, And Information Science;   

DOI  :  10.2172/1042920
RP-ID  :  ORNL/TM-2012/194
RP-ID  :  DE-AC05-00OR22725
RP-ID  :  1042920

美国|英语

来源: UNT Digital Library

【 摘 要 】

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.