Approximating the Range Sum of a Graph on CREW PRAM

摘要

In this paper we have studied the problem of finding the range sum of a graph G =< V, E > which is to color the vertices of a graph with ranges from a specified set in such a way that adjacent vertices are colored with non-overlapping ranges and the sum of the lengths of the ranges is the maximum possible. The problem of finding a good approximation to the range sum is often encountered in many engineering problems. We have presented an efficient parallel algorithm for computing an approximate solution to the range sum problem of a graph on CREW PRAM.