In a complete directed weighted graph there are jobs located at nodes of the graph. Job i has an associated processing time or handling time h/sub i/, and the job must start within a prespecified time window [r/sub i/, d/sub i/]. A vehicle can move on the arcs of the graph, at unit speed and that has to execute the jobs within their respective time windows. We consider three different problems on the CREW PRAM. (1) Find the minimum cost routes between all pairs of nodes in a network. We give an O(log/sup 3/ n) time algorithm with n/sup 4//log/sup 2/ n processors. (2) Services all locations in minimum time. The general problem is NP-complete but O(n/sup 2/) time algorithms are known for a special case; for this case we obtain an O(log/sup 3/ n) time parallel algorithm using n/sup 4//log/sup 2/ n processors and a linear time optimal parallel algorithm. (3) Minimize the sum of waiting times at all locations. The general problem is NP-complete but O(n/sup 2/) time algorithm are known for a special case; for this case, we obtain an O(log/sup 2/ n) time algorithm with n/sup 3//log n processors and also a linear time optimal parallel algorithm.

The longest common subsequence problem is to find a substring that is common to two given strings and is at least as long as any other such string. If m and n are the lengths of the two strings (m<2), we obtain O(log m) time parallel algorithm with mn processors and an O(log/sup 2/ n) time optimal parallel algorithm. Serial complexity on the decision tree model is /spl Theta/(mn).

An algorithm with worst case time complexity O(log/sup 2/N) in two dimensions and O(m/sup 1/2/log N) in three dimensions with N input points and m as the number of tetrahedra in triangulation is given. Its AT/sup 2/ VLSI complexity on Thompson's logarithmic delay model, (1983) is O(N/sup 2/log/sup 6/N) in two dimensions and O(m/sup 2/Nlog/sup 4/ N) in three dimensions.>