Browse Prior Art Database

Multiprocessor Implementation Scheme for Graph Optimization Problems

IP.com Disclosure Number: IPCOM000035649D
Original Publication Date: 1989-Jul-01
Included in the Prior Art Database: 2005-Jan-28

Publishing Venue

IBM

Related People

Authors:
Natarajan, KS [+details]

Abstract

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.