The center problem of a graph is motivated by a number of facility location problems. In this paper, we propose parallel algorithms for finding the center of interval graphs and circular-arc graphs. Our algorithms run in O(log n) time algorithm using O(n/log n) processors while the intervals and arcs are given in sorted order. Our algorithms are on the EREW PRAM model.

Based on the dimensionality reduction technique and the solution for proximate points problem, we achieve the optimality of the three-dimensional Euclidean distance transform (3D_EDT) computation. For an N N N binary image, our algorithms for both 3D_EDT and its applications can be performed in O (log log N) time using CRCW processors or in O (log N) time using EREW processors. To the best of our knowledge, all results described above are the best known. As for the n-dimensional Euclidean distance transform (nD_EDT) and its applications of a binary image of size Nn, all of them can be computed in O (nlog log N) time using CRCW processors or in O (nlog N) time using EREW processors.