Narrow Results

Evidence is given to suggest that minimally vertex colouring an interval graph may not be in NC¹. This is done by showing that 3-colouring a linked list is NC¹-reducible to minimally colouring an interval graph. However, it is shown that an interval graph with a known interval representation and an O(1) chromatic number can be minimally coloured in NC¹.

For the CRCW PRAM model, an o(log n) time, polynomial processors algorithm is obtained for minimally colouring an interval graph with o(log n) chromatic number and a known interval representation. In particular, when the chromatic number is O((log n)^1-ε), 0<ε<1, the algorithm runs in O(log n/log log n) time. Also, an O(log n) time, O(n) cost, EREW PRAM algorithm is found for interval graphs of arbitrary chromatic numbers. The following lower bound result is also obtained: even when the left and right endpoints of the interval are separately sorted, minimally colouring an interval graph needs Ω(log n/log log n) time, on a CRCW PRAM, with a polynomial number of processors.

In this paper, a parallel algorithm for all nearest smallers problem without using doubly logarithmic tree is described. It is shown that using only $O(loglogn)$ time routines for merging and prefix minima, we can easily get an $O(loglogn)$ time parallel algorithm for the all Nearest Smallers problem.

We prove that prefix sums of n integers of at most b bits can be found on a COMMON CRCW PRAM in time with a linear time-processor product. The algorithm is optimally fast, for any polynomial number of processors. In particular, if the time taken is . This is a generalisation of previous result. The previous time algorithm was valid only for O(log n)-bit numbers. Application of this algorithm to r-way parallel merge sort algorithm is also considered.

We also consider a more realistic PRAM variant, in which the word size, m, may be smaller than b (m≥log n). On this model, prefix sums can be found in optimal time.