# Minimum Spanning Tree Verification, Fast Priority Queues, and Massively Parallel Factoring (Thesis)

#### Abstract:

We present algorithms for problems from three different areas of

research on parallel computation. The first problem that we consider

is verifying minimum spanning trees. Given a weighted, undirected

graph $G$ and a spanning tree $T$ of $G$, our algorithms determine

whether $T$ is a minimum spanning tree. We present the first linear

time algorithm for this problem, that is, if $G$ has $n$ vertices and

$m$ edges, our algorithm runs in $O(m + n)$ time given a unit cost

random access machine (RAM) with $O(log n)$ word size. Along with

the spanning tree verification problem, we consider the spanning tree

sensitivity analysis problem. This problem is to determine the

maximum possible change for each individual edge cost that does not

destroy the minimality of the given spanning tree. We give two

algorithms for this problem: the first runs in $O(m+n)$ expected time

and the second runs in optimal deterministic time, but the exact time

bound is not known.

We additionally present optimal parallel algorithms for the minimum

spanning tree verification and sensitivity analysis problems. The

parallel algorithms share top level ideas with the above sequential

algorithms, but their implementations require different techniques.

The parallel verification algorithm runs in $O(log n)$ time using

$Theta((m+n)/log n)$ processors in the concurrent read, exclusive

write (CREW) PRAM model. The parallel sensitivity analysis algorithms

are the parallel equivalents of the sequential sensitivity analysis

algorithms; we give an algorithm that runs in $O(log n)$ expected

time using $Theta((m+n)/log n)$ CREW processors and a deterministic

algorithm that run is optimal but unknown time using

$Theta((m+n)/log n)$ processors as well.

The second problem that we consider is that of allowing concurrent

operations on a priority queue over some bounded universe. Given a

bounded universe, say $[0 ldots N]$, we give algorithms for

performing insertions, deletions and find minimum operations on a set

of elements from the universe. Each operation completes in $O(log

log N)$ time. Our algorithms are unique because the operations can

be pipelined in such a way that a new operation can always begin on

the set in a constant amount of time. This allows concurrent

operations on the set and gives a way to increase the throughput of

the data structure without increasing the latency of any single

operation. We give an application of this data structure to the

longest increasing subsequence problem, giving an optimal linear time

algorithm using $Theta(log log N)$ processors.

The last problem we consider is that of factoring integers. Our

contribution to this widely studied problem is to give efficient

factoring algorithms for massively parallel single instruction,

multiple data (SIMD) machines. The algorithms presented here have

been implemented on a 16K processor MasPar SIMD machine. We present

both special purpose factoring algorithms (where the running time

depends strongly on the size of the smallest factor) and general

purpose methods (where the running time depends solely on the size of

the integer to be factored). Additionally we present fast algorithms

for the multiplication of large integers modulo a fixed integer, a

problem useful for many applications in the area of computational

number theory and cryptography.