PARALLEL ALGORITHMS FOR THE DOMINATION PROBLEMS IN TRAPEZOID GRAPHS

Trapezoid graphs are a superclass of permutation graphs and interval g raphs. This paper presents first parallel algorithms for the independe nt domination, total domination, connected domination and domination p roblems in weighted trapezoid graphs. All these algorithms take O(log( 2)n) time on a EREW PRAM. The number of processors required is O(max{n (3)/log(2)n,n(2.376)}) for the independent domination problem, and O(m ax{nm(2)/log(2)n,m(2.376)}) for the other domination problems, where m is the number of edges in a trapezoid graph of n vertices.