Multiprocessor Implementation Scheme for Graph Optimization Problems
Original Publication Date: 1989-Jul-01
Included in the Prior Art Database: 2005-Jan-28
A general scheme for implementing parallel algorithms for solving a variety of graph optimization problems using a multiprocessor is described. The basic parallel processing scheme for solving the graph problems is outlined below: 1. Identify an efficient divide-and-conquer serial algorithm for solving the problem (the serial algorithm works by partitioning the input data among the subproblems). 2. Partition the data for the given problem as dictated by the divide phase of the sequential algorithm. 3. Solve several subproblems simultaneously by allocating one or more processors to each subproblem until all subproblems are solved. 4. Combine the results of the subproblems and obtain a solution to the original problem.