Concurrent threads and optimal parallel minimum spanning trees algorithm.
This paper resolves a long-standing open problem on whether the concurrent write capability of parallel random access machine (PRAM) is essential for solving fundamental graph problems like connected components and minimum spanning trees in O(logn) time. Specifically, we present a new algorithm to solve these problems in O(logn) time using a linear number of processors on the exclusive-read exclusive-write PRAM. The logarithmic time bound is actually optimal since it is well known that even computing the OR of nbit requires &OHgr;(log n time on the exclusive-write PRAM. The efficiency achieved by the new algorithm is based on a new schedule which can exploit a high degree of parallelism.
INTRODUCTION
Given a weighted undirected graph G with n vertices and m edges, the minimum
spanning tree (MST) problem is to nd a spanning tree (or spanning forest) of G
with the smallest possible sum of edge weights. This problem has a rich history.
A preliminary version of this paper appeared in the proceedings of the Tenth Annual ACM-SIAM
Symposium on Discrete Algorithms (Baltimore, Maryland). ACM, New York, SIAM, Philadel-
phia, pp. 225-234.
This work was supported in part by Hong Kong RGC Grant HKU-289/95E.
Address: Ka Wong Chong and Tak-Wah Lam, Department of Computer Science and Information
Systems, The University of Hong Kong, Hong Kong. Email: fkwchong,twlamg@csis.hku.hk; Yijie
Han, Computer Science Telecommunications Program, University of Missouri { Kansas City, 5100
Rockhill Road, Kansas, MO 64110, USA. Email: han@cstp.umkc.edu.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is
granted without fee provided that copies are not made or distributed for prot or direct commercial
advantage and that copies show this notice on the rst page or initial screen of a display along
with the full citation. Copyrights for components of this work owned by others than ACM must
be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on
servers, to redistribute to lists, or to use any component of this work in other works, requires prior
specic permission and/or a fee. Permissions may be requested from Publications Dept, ACM
Inc., 1515 Broadway, New York, NY 10036 USA, fax +1 (212) 869-0481, or permissions@acm.org.
Han, and T.W. Lam
Sequential MST algorithms running in O(m log n) time were known a few decades
ago (see Tarjan [1983] for a survey). Subsequently, a number of more e-cient MST
algorithms have been published. In particular, Fredman and Tarjan [1987] gave an
algorithm running in O(m(m;n)) time, where (m; n) = minfi j log (i) n  m=ng.
This time complexity was improved to O(m log (m; n)) by Gabow, Galil, Spencer,
and Tarjan [1986]. Chazelle [1997] presented an even faster MST algorithm with
time complexity O(m(m;n) log (m; n)), where (m; n) is the inverse Ackerman
function. Recently, Chazelle [1999] improved his algorithm to run in O(m(m;n))
time, and later Pettie [1999] independently devised a similar algorithm with the
same time complexity. More recently, Pettie and Ramachandran [2000] obtained
an algorithm running in optimal time. A simple randomized algorithm running in
linear expected time has also been found [Karger et al. 1995].
In the parallel context, the MST problem is closely related to the connected component
(CC) problem, which is to nd the connected components of an undirected
graph. The CC problem actually admits a faster algorithm in the sequential con-
text, yet the two problems can be solved by similar techniques on various models
of parallel random access machines (see the surveys by JaJa [1992] and Karp and
Ramachandran [1990]). With respect to the model with concurrent write capability
(i.e., processors can write into the same shared memory location simultaneously),
both problems can be solved in O(log n) time using n+m processors [Awerbuch and
Shiloach 1987; Cole and Vishkin 1986]. Using randomization, Gazit's algorithm
[1986] can solve the CC problem in O(log n) expected time using (n
processors. The work of this algorithm (dened as the time-processor product) is
O(n +m) and thus optimal. Later, Cole et al. [1996] obtained the same result for
the MST problem.
For the exclusive write models (including both concurrent-read exclusive-write
and exclusive-read exclusive-write PRAMs), O(log 2 n) time algorithms for the CC
and MST problems were developed two decades ago [Chin et al. 1982; Hirschberg
et al. 1979]. For a while, it was believed that exclusive write models could not
overcome the O(log 2 n) time bound. The rst breakthrough was due to Johnson
and Metaxas [1991, 1992]; they devised O(log 1:5 n) time algorithms for the CC
problem and the MST problem. These results were improved by Chong and Lam
[1993] and Chong [1996] to O(log n loglog n) time. If randomization is allowed, the
time or the work can be further improved. In particular, Karger et al. [1995] showed
that the CC problem can be solved in O(log n) expected time, and later Halperin
and Zwick [1996] improved the work to linear. For the MST problem, Karger [1995]
obtained a randomized algorithm using O(log n) expected time (and super-linear
work), and Poon and Ramachandran [1997] gave a randomized algorithm using
linear expected work and O(log n  log log n  2 log  n ) expected time.
Another approach stems from the fact that deterministic space bounds for the
st-connectivity problem immediately imply identical time bounds for EREW algorithms
for the CC problem. Nisan et al. [1992] have shown that st-connectivity
problem can be solved deterministically using O(log 1:5 n) space, and Armoni et al.
[1997] further improved the bound to O(log 4=3 n). These results imply EREW
algorithm for solving the CC problem in O(log 1:5 n) time and O(log 4=3 n) time,
respectively.
Optimal Parallel MST Algorithm  3
Prior to our work, it had been open whether the CC and MST problems could be
solved deterministically in O(log n) time on the exclusive write models. Notice that
(log n) is optimal since these graphs problems are at least as hard as computing
the OR of n bits. Cook et al. [1986] have proven that the latter
requires
qui n)
time on the CREW or EREW PRAM no matter how many processors are used.
Existing MST algorithms (and CC algorithms) are di-cult to improve because of
the locking among the processors. As the processors work on dierent parts of the
graph having dierent densities, the progress of the processors is not uniform, yet
the processors have to coordinate closely in order to take advantage of the results
computed by each other. As a result, many processors often wait rather than doing
useful computation. This paper presents a new parallel paradigm for solving the
MST problem, which requires minimal coordination among the processors so as to
fully utilize the parallelism. Based on new insight into the structure of minimum
spanning trees, we show that this paradigm can be implemented on the EREW,
solving the MST problem in O(log n) time using n +m processors. The algorithm
is deterministic in nature and does not require special operations on edge weights
(other than comparison).
Finding connected components or minimum spanning trees is often a key step in
the parallel algorithms for other graph problems (see e.g., Miller and Ramachandran
[1986]; Maon et al. [1986]; Tarjan and Vishkin [1985]; Vishkin [1985]). With
our new MST algorithm, some of these parallel algorithms can be immediately
improved to run in optimal (i.e., O(log n)) time without using concurrent write
(e.g., biconnectivity [Tarjan and Vishkin 1985] and ear decomposition [Miller and
Ramachandran 1986]).
From a theoretical point of view, our result illustrates that the concurrent write
capability is not essential for solving a number fundamental graph problems ef-
ciently. Notice that EREW algorithms are actually more practical in the sense
that they can be adapted to other more realistic parallel models like the Queuing
Shared Memory (QSM) [Gibbons et al. 1997] and the Bulk Synchronous Parallel
(BSP) model [Valaint 1990]. The latter is a distributed memory model of parallel
computation. Gibbon et al. [1997] showed that an EREW PRAM algorithm can be
simulated on the QSM model with a slow down by a factor of g, where g is the band-width
parameter of the QSM model. Such a simulation is, however, not known for
the CRCW PRAM. Thus, our result implies that the MST problem can be solved
e-ciently on the QSM model in O(g log n) time using a linear number of processors.
Furthermore, Gibbon et al. [1997] derived a randomized work-preserving simulation
of a QSM algorithm with a logarithmic slow down on the BSP model.
The rest of the paper is organized as follows. Section 2 reviews several basic
concepts and introduces a notion called concurrent threads for nding minimum
spanning trees in parallel. Section 3 describes the schedule used by the threads,
illustrating a limited form of pipelining (which has a
avor similar to the pipelined
merge-sort algorithm by Cole [1988]). Section 4 lays down the detailed requirement
for each thread. Section 5 shows the details of the algorithm. To simplify the
discussion, we rst focus on the CREW PRAM, showing how to solve the MST
problem in O(log n) time using (n m) log n processors. In Section 6 we adapt
algorithm to run on the EREW PRAM and reduce the processor bound to linear.
4  K.W. Chong, Y. Han, and T.W. Lam
Remark: Very recently, Pettie and Ramachandran [1999] made use of the result
in this paper to further improve existing randomized MST algorithms. Precisely,
their algorithm is the rst one to run, with high probability, in O(log n) time and
linear work on the EREW PRAM.
2. BASICS OF PARALLEL MST ALGORITHMS: PAST AND PRESENT
In this section we review a classical approach to nding an MST. Based on this
approach, we can easily contrast our new MST algorithm with existing ones.
We assume that the input graph G is given in the form of adjacency lists. Consider
any edge G. Note that e appears in the adjacency lists of u and
v. We call each copy of e the mate of the other. When we need to distinguish
them, we use the notations hu; vi and hv; ui to signify that the edge originates from
respectively. The weight of e, which can be any real number, is denoted
by w(e) or w(u; v). Without loss of generality, we assume that the edge weights
are all distinct. Thus, G has a unique minimum spanning tree, which is denoted
by T
G throughout this paper. We also assume that G is connected (otherwise, our
algorithm nds the minimum spanning forest of G).
Let B be a subset of edges in G which contains no cycle. B induces a set of trees
in a natural sense|Two vertices in G are in the same tree if
they are connected by edges of B. If B contains no edge incident on a vertex v,
then v itself forms a tree.
Denition: Consider any edge in G and any tree T 2 F . If both u
and v belong to T , e is called an internal edge of T ; if only one of u and v belongs
to T , e is called an external edge. Note that an edge of T is also an internal edge
of T , but the converse may not be true.
Denition: B is said to be a -forest if each tree T 2 F has at least  vertices.
For example, if B is the empty set then B is a 1-forest of G; a spanning tree such
as T
G is an n-forest. Consider a set B of edges chosen from T
G . Assume that B is
a -forest. We can augment B to give a 2-forest using a greedy
be an arbitrary subset of F such that F 0 includes all trees T 2 F with fewer than
vertices may contain trees with 2 or more vertices). For every tree in F 0 ,
we pick its minimum external edge. Denote B 0 as this set of edges.
Lemma 1. [JaJa 1992, Lemma 5.4] B 0 consists of edges in T
G only.
Lemma 2. is a 2-forest.
Proof. Every tree in F F 0 already contains at least 2 vertices. Consider a
tree T in F 0 . Let hu; vi be the minimum external edge of T , where v belongs to
another tree T 0 2 F . With respect to all the vertices in T and T 0 are
connected together. Among the trees induced by there is one including
T and T 0 , and it contains at least 2 vertices. Therefore, is a 2-forest of
G.
Based on Lemmas 1 and 2, we can nd T
G in blog nc stages as follows:
Notation: Let B[p; q] denote [ q
and the empty set otherwise.
Optimal Parallel MST Algorithm  5
procedure
(1) for to blog nc do /* Stage i */
(a) Let F be the set of trees induced by B[1; i 1] on G. Let F 0 be an
arbitrary subset of F such that F 0 includes all trees T 2 F with
fewer than 2 i vertices.
e is the minimum external edge of T 2 F 0 g
(2) return B[1; blog nc].
At Stage i, dierent strategies for choosing the set F 0 in Step 1(a) may lead
to dierent B i 's. Nevertheless, B[1; i] is always a subset of T
G and induces a 2 i -
forest. In particular, B[1; blog nc] induces a 2 blog nc -forest, in which each tree, by
denition, contains at least 2 blog nc > n=2 vertices. In other words, B[1; blog nc]
induces exactly one tree, which is equal to T
G . Using standard parallel algorithmic
techniques, each stage can be implemented in O(log n) time on the EREW PRAM
using a linear number of processors (see e.g., JaJa [1992]). Therefore, T
G can
be found in O(log 2 n) time. In fact, most parallel algorithms for nding MST
(including those CRCW PRAM algorithms) are based on a similar approach (see
e.g., Awerbuch and Shiloach [1987]; Chin et al. [1982]; citeNcv86; Johnson and
Metaxas [1991, 1992]; Chong and Lam [1993]; Chong [1996]; Karger et al. [1995]).
These parallel algorithms are \sequential" in the sense that the computation of B i
starts only after B i 1 is available (see Figure 1(a)).
An innovative idea exploited by our MST algorithm is to use concurrent threads
to compute the B i 's. Threads are groups of processors working on dierent tasks,
the computation of the threads being independent of each other. In our algorithm,
there are blog nc concurrent threads, each nding a particular B i . These threads
are characterized by the fact that the thread for computing B i starts long before
the thread for computing B i 1 is completed, and actually outputs B i in O(1) time
after Figure 1(b)). As a result, T
G can be found in O(log n)
time.
Our algorithm takes advantage of an interesting property of the sets
. This property actually holds with respect to most of the deterministic
algorithms for nding an MST, though it has not mentioned explicitly in the literature

Lemma 3. Let T be one of the trees induced by B[1; k], for any 0  k  blog nc.
e T be the minimum external edge of T . For any subtree (i.e., connected sub-
of T , the minimum external edge of S is either e T or an edge of T .
Proof. See Appendix.
3.

OVERVIEW

AND SCHEDULE
Our algorithm consists of blog nc threads running concurrently. For 1  i  blog nc,
Thread i aims to nd a set B i which is one of the possible sets computed at Stage i
of the procedure Iterative-MST. To be precise, let F be the set of trees induced by
be an arbitrary subset of F including all trees with fewer than
contains the minimum external edges of the trees in F 0 . Thread i
6  K.W. Chong, Y. Han, and T.W. Lam
Phase 2
Phase 1
Phase 1
Phase 1
Phase 2
Phase 1
Phase 2
Phase 1
(b)
Thread
Phase blog ic
Phase blog(i 1)c
Fig. 1. (a) The iterative approach. (b) The concurrent-thread approach.
receives the output of Threads 1 to i 1 (i.e., incrementally, but
never looks at their computation. After in a
further of O(1) time.
3.1 Examples
Before showing the detailed schedule of Thread i, we give two examples illustrating
how Thread i can speed up the computation of B i . In Examples 1 and 2, Thread i
computes B i in time ci and 1
respectively after Thread (i
where c is some xed constant. To simplify our discussion, these examples assume
that the adjacency lists of a set of vertices can be \merged" into a single list in
time. At the end of this section, we will explain why this is infeasible in our
implementation and highlight our novel observations and techniques to evade the
problem.
Thread i starts with a set Q 0 of adjacency lists, where each list contains the
smallest edges incident on a vertex in G. The edges kept in Q 0 are already
su-cient for computing B i . The reason is as follows: Consider any tree T induced
by Assume the minimum external edge e T of T is incident on a vertex
v of T . If T contains fewer than 2 i vertices, at most 2 i 2 edges incident on v are
internal edges of T . Thus, the 2 i 1 smallest edges incident on v must include e T .
Example 1: This is a straightforward implementation of Lemma 2. Thread i
starts only when are all available. Let F be the set of trees induced
by B[1; i 1]. Suppose we can merge the adjacency lists of the vertices in each tree,
forming a single combined adjacency list. Notice hat if a tree in F has fewer than
vertices, its combined adjacency list will contain at most (2 i edges. For
Optimal Parallel MST Algorithm  7
each combined list with at most (2 i edges, we can determine the minimum
external edge in time ci, where c is some suitable constant. The collection of such
minimum external edges is reported as B i . We observe that a combined adjacency
list with more than edges represents a tree containing at least 2 i vertices.
By the denition of B i , it is not necessary to report the minimum external edge of
such a tree.
Example 2: This example is slightly more complex, illustrating how Thread i
works in an \incremental" manner. Thread i starts o as soon as B i=2 has been
computed. At this point, only are available and Thread i is not ready
to compute B i . Nevertheless, it performs some preprocessing (called Phase I below)
so that when B become available, the computation of B i can be
speeded up to run in time 1
2 ci only (Phase II).
Phase I: Let F 0 be the set of trees induced by B[1; i=2]. Again, suppose we can
merge the adjacency lists in Q 0 for every tree in F 0 , forming another set Q 0 of
adjacency lists. By the denition of B[1; i=2], each tree in F 0 contains at least 2 i=2
vertices. For each tree in F 0 with fewer than 2 i vertices, its combined adjacency list
contains at most (2 i 1) 2 edges. We extract from the list the 2 i=2 1 smallest edges
such that each of them connects to a distinct tree in F 0 . These edges are su-cient
for nding B i (the argument is an extension of the argument in Example 1). The
computation takes time ci only.
Phase II: When B are available, we compute B i based on Q 0 as
follows: Edges in B[i=2 further connect the trees in F 0 , forming a set F
of bigger trees. Suppose we can merge the lists in Q 0 for every tree in F . Notice
that if a tree in F contains fewer than 2 i vertices, it is composed of at most 2 i=2 1
trees in F 0 and its combined adjacency list contains no more than (2 i=2 1) 2 edges.
In this case, we can nd the minimum external edge in at most a further of 1
time. B i is the set of minimum external edges just found. In conclusion, after
is computed, B i is found in time 1
Remark: The set B i found by Examples 1 and 2 may be dierent. Yet in either
case, is a subset of T
G and a 2 i -forest.
3.2 The schedule
Our MST algorithm is based on a generalization of the above ideas. The computation
of Thread i is divided into blog ic phases. When Thread i 1 has computed
is about to enter its last phase, which takes O(1) to report B i . See

Figure

1(b).
Globally speaking, our MST algorithm runs in blog nc supersteps, where each
lasts O(1) time. In particular, Thread i delivers B i at the end of the ith
superstep. Let us rst consider i a power of two. Phase 1 of Thread i starts at the
are available. The computation takes
no more than i=4 supersteps, ending at the (i=2 starts
at the (i=2 are available)
and uses i=8 supersteps. Each subsequent phase uses half as many supersteps as
the preceding phase. The last phase (Phase log i) starts and ends within the ith
superstep. See Figure 2.
For general i, Thread i runs in blog ic phases. To mark the starting time of each
8  K.W. Chong, Y. Han, and T.W. Lam1 2 i+ 1 i+ ii+ i+ iPhase log i
Phase 1 Phase 2 Thread i
Fig. 2. The schedule of Thread i, where i is a power of 2.
phase, we dene the sequence
(That is, a Phase j of Thread i, where 1  j
blog ic, starts at the (a 1)th superstep and uses a j+1 a
supersteps. Phase j has to handle the edge sets B a j 1
are made available by other threads during the execution of Phase (j 1).
3.3 Merging
In the above examples, we assume that for every tree in F , we can merge the
adjacency lists of its vertices (or subtrees in Phase II of Example 2) into a single
list e-ciently and the time does not depend on the total length. This can be
done via the technique introduced by Tarjan and Vishkin [1985]. Let us look at
an example. Suppose a tree T contains an edge e between two vertices u and v.
Assume that the adjacency lists of u and v contain e and its mate respectively.
The two lists can be combined by having e and its mate exchange their successors
(see

Figure

3). If every edge of T and its mate exchange their successors in their
adjacency lists, we will get a combined adjacency list for T in O(1) time. However,
the merging fails if any edge of T or its mate is not included in the corresponding
adjacency lists.
In our algorithm, we do not keep track of all the edges for each vertex (or subtree)
because of e-ciency. For example, each adjacency list in Q 0 involves only
edges incident on a vertex. With respect to a tree T , some of its edges and their
mates may not be present in the corresponding adjacency lists. Therefore, when
applying the O(1)-time merging technique, we may not be able to megre the adjacency
lists into one single list for representing T . Failing to form a single combined
adjacency list also complicates the extraction of essential edges (in particular, the
minimum external edges) for computing the set B i . In particular, we cannot easily
determine all the vertices belonging to T and identify the redundant edges, i.e.,
internal and extra multiple external edges, in the adjacency list of T .
e
e
e
e
Fig. 3. Merging a pair of adjacency lists Lu and Lv with respect to a common edge e.
Optimal Parallel MST Algorithm  9
Actually our MST algorithm does not insist on merging the adjacency lists into a
single list. A key idea here is that our algorithm can maintain all essential edges to
be included in just one particular combined adjacency list. Based on some structural
properties of minimum spanning trees, we can lter out redundant adjacency lists
to obtain a unique adjacency list for T (see Lemmas 5 and 9 in Section 5).
In the adjacency list representing T , internal edges can all be removed using a
technique based on \threshold" [Chong 1996]. The most intriguing part concerns
the extra multiple external edges. We nd that it is not necessary to remove all of
them. Specically, we show that those extra multiple external edges that cannot
be removed \easily" must have a bigger weight and their presence does not aect
the correctness of the computation.
In the next section, we will elaborate on the above ideas and formulate the
requirements for each phase so as to achieve the schedule.
4. REQUIREMENTS FOR A PHASE
In this section we specify formally what Thread i is expected to achieve in each
phase. Initially (in Phase 0), Thread i constructs a set Q 0 of adjacency lists. For
each vertex v in G, Q 0 contains a circular linked list L including the 2 i 1 smallest
edges incident on v. In addition, L is assigned a threshold, denoted by h(L). If
L contains all edges of v, is the
smallest edge truncated from L. In each of the blog ic phases, the adjacency lists
are further merged based on the newly arrived edge sets, and truncated according
to the length requirement. For each combined adjacency list, a new threshold
is computed. Intuitively, the threshold records the smallest edge that has been
truncated so far.
Consider Phase j, where 1  j  blog ic. It inherits a set Q j 1 of adjacency
lists from Phase j 1 and receives the edge sets B[a (recall that a
denote the set of trees induced by B[1; a j ]. Phase j aims at
producing a set Q j of adjacency lists capturing the external edges of the trees in
F j that are essential for the computation of B i . Basically, we try to merge the
adjacency lists in Q j 1 with respect to B[a As mentioned before, this
merging process may produce more than one combined adjacency list for each tree
Nevertheless, we strive to ensure that only one combined list is retained to
. the rest are ltered out. In view of the time constraint imposed by the
schedule of Thread i, we also need a tight bound on the length of each remaining
adjacency list.
Let L be a list in Q j .
R1. uniquely corresponds to a tree T 2 F j , storing only
the external edges of T . In this case, T is said to be represented by L in Q j .
Some trees in F j may not be represented by any lists in Q
with fewer than 2 i vertices are represented.
R2. (length): L contains at most 2 bi=2 j c 1 edges.
We will dene what edges of a tree T 2 F j are essential and must be included
in L. Consider an external edge e of T that connects to another tree T 0 2 F j . We
Han, and T.W. Lam
say that e is primary if, among all edges connecting T and T 0 , e has the smallest
weight. Otherwise, e is said to be secondary. Note that if the minimum spanning
tree of G contains an edge which is an external edge of both T and T 0 , it must be a
primary one. Ideally, only primary external edges should be retained in each list of
. Yet this is infeasible since Thread i starts truncated adjacency lists
and we cannot identify and remove all the secondary external edges in each phase.
(Removing all internal edges, though non-trivial, is feasible.)
An important observation is that it is not necessary to remove all secondary external
edges. Based on a structural classication of light and heavy edges (dened
below), we nd that all light secondary external edges can be removed easily. Af-
terwards, each list contains all the light primary external edges and possibly some
heavy secondary external edges. The set of light primary external edges may not
cover all primary external edges and its size can be much smaller than 2 bi=2 j c 1.
Yet we will show that the set of light primary external edges su-ces for computing
and the presence of heavy secondary external edges does not aect the
correctness.
Below we give the denition of light and heavy edges, which are based on the
notion of base.
Denition: Let T be a tree in F j .
Let
be any real number. A tree T 0 2 F j is said to be
-accessible to T if
or there is another tree T 00 2 F j such that T 00 is
-accessible to T and connected
to T 0 by an edge with weight smaller than
Let e be an external (or internal) edge of T . Dene to be the set
is w(e)-accessible to Tg. The size of base(F
by is the total number of vertices in the trees involved.
Let e be an external (or internal) edge of T . We say that e is light if kbase(F
It follows from the above denition that a light edge of a tree T has a smaller
weight than a heavy edge of T . Also, a heavy edge of T will remain a heavy edge
in subsequent phases. More specically, in any Phase k where k > j, if T is a
subtree of some tree X 2 F k , then for any external (or internal) edge e of T ,
Therefore, if e is heavy with respect to T then
it is also heavy with respect to X .
The following lemma gives an upper bound on the number of light primary external
edges of each tree in F j , which complies with the length requirement of the
lists in Q j .
Lemma 4. Any tree T 2 F j has at most 2 bi=2 j c 1 light primary external edges.
Proof. Let x be the number of light primary external edges of T . Among the
light primary external edges of T , let e be the one with the biggest weight. The
set includes T and at least x 1 trees adjacent to T . As B[1; a j ] is a
2 a j -forest, every tree in F j contains at least 2 a j vertices. We have
. By denition of a light edge,
Thus, x  2 a j < 2 i and x < 2 i a
Optimal Parallel MST Algorithm  11
The following requirement species the essential edges to be kept in each list of
characterizes those secondary external edges, if any, in each list.
R3. (base) Let T be the tree in F j represented by a list L 2 Q j . All light
primary external edges of T are included in L, and secondary external edges
of T , if included in L, must be heavy.
Retaining only the light primary external edges in each list of Q j is already sufcient
for the computation of B i . In particular, let us consider the scenario at the
end of Phase blog ic. For any tree T s 2 F blog ic with fewer than 2 i vertices, the minimum
external edge e Ts of T s must be reported in B i . Note that base(F blog ic
contains Ts is a light primary external
edge of T s . In all previous phases k, F k contains a subtree of T s , denoted by
W , of which e Ts is an external edge. Note that e Ts is also a light primary external
edge of W (as a heavy edge remains a heavy edge subsequently).
On the other hand, at the end of Phase blog ic, if a tree T x 2 F blog ic contains 2 i or
more vertices, all its external edges are heavy and R3 cannot enforce the minimum
external edge e Tx of T x being kept in the list for T x . Fortunately, it is not necessary
for Thread i to report the minimum external edge for such a tree. The following
requirements for the threshold help us detect whether the minimum external edge
of T x has been removed. If so, we will not report anything for T x . Essentially, we
require that if e Tx or any primary external edge e of T x has been removed from
the list L x that represents T x , the threshold kept in L x is no bigger than w(e
(respectively, w(e)). Then the smallest edge in L x is e Tx if and only if its weight is
fewer than the threshold.
Let T be a tree in F j represented by a list L 2 Q j . The threshold of L
satises the following properties.
R4. (lower bound for the threshold) If h(L) 6= 1, then h(L) is equal to the
weight of a heavy internal or external edge of T .
R5. (upper bound for the threshold) Let e be an external edge of T not
included in L. If e is primary, then h(L)  w(e).
(Our algorithm actually satises a stronger requirement that h(L)  w(e) if
e is primary, or
e is secondary and the mate of e is still included in another list L 0 in Q j .)
In summary, R1 to R5 guarantee that at the end of Phase blog ic, for any tree
if T has fewer than 2 i vertices, its minimum external edge e T is the
only edge kept in a unique adjacency list representing T ; otherwise, T may or may
not be represented by any list. If T is represented by a list but e T has already been
removed, the threshold kept is at most w(e T ). Every external edge currently kept
in the list must have a weight greater than or equal to the threshold. Thus, we can
simply ignore the list for T .
It is easy to check that Q 0 satises the ve requirements for Phase 0. In the next
section we will give an algorithm that can satisfy these requirements after every
phase. Consequently, Thread i can report B i based on the edges in the lists in
12  K.W. Chong, Y. Han, and T.W. Lam
5. THE ALGORITHM
In this section we present the algorithmic details of Thread i, showing how to
merge and extract the adjacency lists in each phase. The discussion is inductive in
nature|for any j  1, we assume that Phase j 1 has produced a set of adjacency
lists satisfying the requirements R1-R5, and then show how Phase j computes a
new set of adjacency lists satisfying the requirements in O(i=2 j using a linear
number of processors.
Phase j inherits the set of adjacency lists Q j 1 from Phase j 1 and receives
the edges B[a To ease our discussion, we refer to B[a
INPUT. Notice that a list in Q represents one of the trees in F j 1 (recall that
denote the set of trees induced by B[1; a
Phase j merges the adjacency lists in Q according to how the trees in F j 1 are
connected by the edges in INPUT.
Consider an edge in INPUT. Denote W 1 and W 2 as the trees in F j 1
containing u and v respectively. Ideally, if e and its mate appear in the adjacency
lists of W 1 and W 2 respectively, the adjacency lists of W 1 and W 2 can be merged
easily in O(1) time. However, W 1 or W 2 might already be too large and not have
a representation in Q j 1 . Even if they are represented, the length requirement of
the adjacency lists may not allow e to be included. As a result, e may appear in
two separate lists in Q or in just one, or even in none; we call e a full, half, and
lost edge respectively. Accordingly, we partition INPUT into three sets, namely
Full-INPUT, Half-INPUT, and Lost-INPUT.
Phase j starts o by merging the lists in Q with respect to edges in Full-INPUT.
Let T be a tree in F j . Let W 1 be the trees in F j 1 that, together with
the edges in INPUT, constitute T . Note that some W i may not be represented by
a list in Q j 1 . Since the merging is done with respect to Full-INPUT, the adjacency
lists of W 1 present, may be merged into several lists instead
of a single one. Let merged lists. Each L i represents a
bigger subtree Z i of T , which is called a cluster below (see Figure 4). A cluster may
contain one or more W i . We distinguish one cluster, called the core cluster, such
that the minimum external edge e T of T is an external edge of that cluster. Note
that the minimum external edge of the core cluster may or may not be e T . For a
non-core cluster Z, the minimum external edge e Z of Z must be a tree edge of T
(by Lemma 3) and thus e Z is in INPUT. Moreover, e Z is not a full edge. Otherwise,
the merging should have operated on e Z , which then becomes an internal edge of a
bigger cluster.
The merged lists obviously need not satisfy the requirements for Q j . In the
following sections, we present the additional processing used to fulll the require-
ments. A summary of all the processing is given in Section 5.4. The discussion
of the processing of the merged lists is divided according to the sizes of the trees,
sketched as follows:
For each tree T 2 F j that contains fewer than 2 i vertices, there is a simple way
to ensure that exactly one merged list is retained in Q j . Edges in that list are
Optimal Parallel MST Algorithm  13
Fig. 4. Each Wx represents a tree in F j 1 . The dotted and solid lines represent half and
full edges in INPUT respectively. T is a tree formed by connecting the trees in F j 1 with
the edges in INPUT. Each Zy (called a cluster) is a subtree of T , formed by connecting
some Wx 's with full edges only. The adjacency lists of the Wx 's within each Zy can be
merged into a single list easily.
ltered to contain all the light primary external edges of T , and other secondary
external edges of T , if included, must be heavy.
For a tree T 0 2 F j that contains at least 2 i vertices, the above processing may
retain more than one merged lists. Here we put in an extra step to ensure that,
except possibly one, all merged lists for T 0 are removed.
The threshold of each remaining list is updated after retaining the 2 bi=2 j c 1
smallest edges. We show that the requirements for the threshold are satised no
matter whether the tree in concern contains fewer than 2 i vertices or not.
5.1 Trees in F j
with fewer than 2 i vertices
In this section we focus on each tree T 2 F j that contains fewer than 2 i vertices.
Denote by the merged lists representing the clusters of T . Observe that
each of these lists contains at most (2 bi=2 edges. Below, we derive an
e-cient way to nd a unique adjacency list for representing T , which contains all
light primary external edges of T .
First of all, we realize that every light primary external edge of T is also a light
primary external edge of a tree W in F j 1 and must be present in the adjacency
list that represents W in Q j 1 (by R3). Thus, all light primary external edges of
T (including the minimum external edge of T ) are present in some merged lists.
Unique Representation: Let L cc be the list in fL such that L cc contains
the minimum external edge e T of T . That is, L cc represents the core cluster
Z 0 of T . Our concern is how to remove all other lists in fL so that T
will be represented uniquely by L cc .
To e-ciently distinguish L cc from other lists, we make use of the properties
14  K.W. Chong, Y. Han, and T.W. Lam
stated in the following lemma. Let L nc be any list in fL g. Let
Z denote the cluster represented by L nc .
Lemma 5. (i) L cc does not contain any edge in Half-INPUT. (ii) L nc contains
at least one edge in Half-INPUT. In particular, the minimum external edge of Z is
in Half-INPUT.
Proof of Lemma 5(i). Assume to the contrary that L cc includes an edge
in Half-INPUT; more precisely, ha; bi is in L cc and hb; ai is not included in any list
in be the trees in F j 1 connected by e, where a 2 W and
. The edge e is a primary external edge of W , as well as of W 0 . Both W
and W 0 are subtrees of T , and W is also a subtree of Z 0 . Below we show that
contains at least 2 i vertices. The latter contradicts
the assumption about T . Thus, Lemma 5(i) follows.
W 0 is a subtree of T and contains less than 2 i vertices. By R1, Q contains
a list LW 0 representing W 0 . By R3, LW 0 contains all light primary external edges
of W 0 . The edge hb; ai is not included in LW 0 and must be heavy. Therefore,
Next, we want to show that all trees in base(F are subtrees of T . Dene
T a and T b to be the subtrees of T constructed by removing e from T (see Figure 5).
Assume that T a contains the vertex a and T b the vertex b. W , as well as Z 0 , is a
a
Fig. 5. T is partitioned into two subtrees Ta and T b , which are connected by e.
subtree of T a , and W 0 is a subtree of T b . By Lemma 3, the minimum external edge
of T b is either e T or e. The former case is impossible because e T is included in L cc
and must be an external edge of Z 0 . Thus, e is the minimum external edge of T b .
By denition of base, base(F cannot include any trees in F j 1 that are
outside T b . In other words, T b includes all subtrees in base(F must
have at least 2 i vertices, and so must T . A contradiction occurs.
Proof of Lemma 5(ii). Let e Z be the minimum external edge of Z. As e Z is a
tree edge of T , it is in INPUT but is not a full edge. In this case, we can further
show that e Z is actually a half edge and included in L nc , thus completing the proof.
Let W be the tree in F j 1 such that W is a component of Z and e Z is an external
edge of W . Note that e Z is primary external edge of W . Let LW denote the
adjacency list in Q representing W . Since e Z is the minimum external edge of
Optimal Parallel MST Algorithm  15
include trees in F j 1 that are outside Z, and thus it
has size less than 2 i . By R3, all light primary external edges of W including e Z are
present in LW . Therefore, e Z is in Half-INPUT, and L nc must have inherited e Z
from LW .
Using Lemma 5, we can easily retain L cc and remove all other merged lists L nc .
One might worry that some L nc might indeed contain some light primary external
edge of T and removing L nc is incorrect. This is actually impossible in view of the
following fact.
Lemma 6. For any external edge e of T that is included in L nc ,
Proof. Let e Z be the minimum external edge of Z. For any external edge e of
T that is included in L nc , e is also an external edge of Z and w(e)  w(e Z ).
Let W and W 0 be the trees in F j 1 connected by e Z such that W 0 is not a
component of Z. As shown in the previous lemma, e Z is in Half-INPUT. Moreover,
e Z is a tree edge of T and is present only in the adjacency list of W . That is, W 0 is
a component of T and the adjacency list of W 0 in Q does not contain e Z . Note
that e Z is a primary external edge of W 0 . By R1 and R3, we can conclude that
e Z is a heavy external edge of W 0 and hence kbase(F Therefore,
By Lemma 6, L nc does not contain any light primary external edge of T . In
other words, all light primary external edges of T must be in L cc , which is the only
list retained.
Excluding All Light Internal and Secondary External Edges: L cc contains all the
light primary external edges of T and also some other edges. Because of the length
requirement (i.e. R2), we retain at most 2 bi=2 j c 1 edges of L cc . Note that the
light primary external edges may not be the smallest edges in L cc . Based on the
following two lemmas, we can remove all other light edges in L cc , which include the
light internal and secondary external edges of T . Then the light primary external
edges of T will be the smallest edges left in the list and retaining the 2 bi=2 j c 1
smallest edges will always include all the light primary external edges.
Lemma 7. Suppose L cc contains a light internal edge hu; vi of T . Then its mate,
hv; ui, also appears in L cc .
Proof. Recall that L cc is formed by merging the adjacency lists of some trees
in F j 1 . By R1, each of these lists does not contain any internal edge of the tree it
represents. If L cc contains a light internal edge hu; vi of T , the edge (u; v) must be
between two trees W and W 0 in F j 1 which are components of Z 0 . Assume that
are light external edges of W and W 0
respectively. Let LW and LW 0 be their adjacency lists in Q j 1 . As hu; vi appears in
appears in LW . By R3, all light edges found in LW , including hu; vi,
must be primary external edges of W . By symmetry, hv; ui is a primary external
edge of W 0 . By R3 again, hv; ui appears in LW 0 . Since L cc inherits the edges from
both LW and LW 0 , we conclude that both hu; vi and hv; ui appear in L cc .
Han, and T.W. Lam
Lemma 8. Suppose L cc contains a light secondary external edge e of T . Let e 0
be the corresponding primary external edge. Then e and e 0 both appear in L cc , and
their mates also both appear in another merged list L 0
cc , where L 0
cc represents the
core cluster of another tree T 0 2 F j .
Proof. Suppose L cc contains a light secondary external edge e of T . Assume
that e connects T to another tree T 0 2 F j , and e 0 is the primary external edge
between T and T 0 . As w(e 0 ) < w(e),
e
Fig. 6. e is a light secondary external edge of T and e 0 is the corresponding primary external
edge.
Thus, e o is also a light primary external edge of T and must be included in L cc . On
the other hand, since e is secondary, is equal to base(F
thus contains less than 2 i
vertices. After merging the lists in Q we obtain a merged list L 0
cc that includes
all light primary external edges of T 0 . Below we show that L 0
cc contains the mates
of e 0 and e.
Observe that kbase(F
both e 0 and e are light external edges of T 0 . As e 0 is also a primary external
edge of T 0 , e 0 (more precisely, its mate) must be included in L 0
cc .
Let W and W 0 be the two trees in F j 1 connected by e, where W is a subtree of
T and W 0 of T 0 . Because e is a light external edge of T and T 0 , it is also a light
external edge of W and W 0 . Note that L cc inherits e from the adjacency list
that represents W . By R3, LW does not include any light secondary
external edge of W , so e is a primary external edge of W . By symmetry, e is also
a primary external edge of W 0 ; thus, by R3, e is in the adjacency list LW
that represents W 0 . Note that L 0
cc must include all the edges of LW 0 as well as
other lists in Q j 1 that contain light external edges of T (see Lemma 6). L 0
cc
contains e, too.
By Lemma 7, we can remove all light internal edges by simply removing edges
whose mates are in the same list. Lemma 8 implies that if L cc contains a light
secondary external edge, the corresponding primary external edge also appears
Optimal Parallel MST Algorithm  17
in L cc and their mates exist in another list L 0
cc . This suggests a simple way to
identify and remove all the light secondary external edges as follows. Without loss
of generality, we assume that every edge in L cc can determine the identity of L cc
(any distinct label given to L cc ). If an edge e 2 L cc has a mate in another list,
say,
cc , e can announce the identity of L cc to its mate and vice versa. By sorting
the edges in L cc with respect to the identities received from their mates, multiple
light external edges connected to the same tree come together. Then we can easily
remove all the light secondary external edges.
Now we know that L cc contains all light primary external edges of T and any
other edges it contains must be heavy. Let us summarize the steps required to build
a unique adjacency list for representing T .
procedure M&C // M&C means Merge and Clean up //
(1) Edges in INPUT that are full with respect to Q j 1 are activated to
merge the lists in Q j 1 . Let Q be the set of merged adjacency lists.
(2) For each merged adjacency list L 2 Q,
(a) if L contains an edge in Half-INPUT, remove L from Q;
(b) detect and remove internal and secondary external edges from L
according to Lemmas 7 and 8.
5.2 Trees with at least 2 i vertices
Consider a tree T 0 2 F j containing 2 i or more vertices. Let L 1 ;    ; L ' be the
merged lists, each representing a cluster of T 0 . Some of these lists may contain
more than (2 edges. Unlike the case in Section 5.1, the minimum
external edge e T 0 of T 0 is heavy, and we cannot guarantee that there is a merged
list containing e T 0 and representing the core clusters of T 0 . Nevertheless, Thread i
can ignore such a tree T 0 , and we may remove all the merged lists. In Lemma 9,
we show that those lists in fL 1 ;    L ' g that represent the non-core clusters of T 0
can be removed easily. If there is indeed a merged list L cc representing the core
cluster, Thread i may not remove L cc . Since T 0 contains at least 2 i vertices and
has no light primary external edge, we have nothing to enforce on L cc regarding
the light primary external edges. The only concern for L cc is the requirements for
the threshold, which will be handled in Section 5.3.
As T 0 contains at least 2 i vertices, any merged list L nc that represents a non-core
cluster of T 0 may not satisfy the properties stated in Lemma 5(ii). We need other
ways to detect such an L nc . First, we can detect the length of L nc . If L nc contains
more than (2 edges, we can remove L nc immediately. Next, if L nc
contains less than (2 edges, we make use of the following lemma to
identify it. Denote h(L) as the threshold associated with a list L 2
merged into L nc g.
Lemma 9. Any list L that represents a non-core cluster
of T 0 satises at least one of the following conditions.
(1) L nc contains an edge in Half-INPUT.
(2) For every edge hu; vi in L nc , either hv; ui is also in L nc or w(u; v)
Han, and T.W. Lam
Proof. Assume that L nc does not contain any edge in Half-INPUT, and L nc
contains an edge hu; vi but does not contain hv; ui. Below we show that w(u; v)
tmp-h(L nc ). The edge (u; v) can be an internal or external edge of Z.
Case 1. (u; v) is an internal edge of Z. L nc inherits hu; vi from a list L 2
be the tree represented by L. By R1, hu; vi is an external edge of W .
Thus, Z includes another tree W 0 2 F j 1 with hv; ui as an external edge, and L nc
also inherits the edges in the list LW that represents W 0 . Note that hv; ui
does not appear in LW 0 . By R5, h(LW 0
have
Case 2. (u; v) is an external edge of Z. It is obvious that w(u; v)  w(e Z ) where
e Z is the minimum external edge of Z. We further show that w(e Z )  tmp-h(L).
be the tree in Z and with e Z as an external edge. Let LW 2
the adjacency list representing W . As mentioned before, e Z is in INPUT and is not
a full edge. If e Z is a lost edge, then L nc does not contain e Z . If e Z is a half edge, L nc
again does not contain e Z because L nc does not contain any edge in Half-INPUT.
In conclusion, e Z does not appear in L nc and hence cannot appear in LW . Since
e Z is a primary external edge of W , we know that, by R5, h(LW )  w(e Z ). By
denition,
Using Lemma 9, we can extend Procedure M&C to remove every merged list L nc
that represents a non-core cluster of any tree T in F j (see Procedure Ext M&C).
Precisely, if T has fewer than 2 i vertices, L nc is removed in Step 2(a); otherwise,
L nc is removed in Step 1(b) or Steps 2(a)-(c).
procedure Ext M&C
(1) (a) Edges in INPUT that are full with respect to Q j 1 are activated
to merge the lists in Q j 1 . Let Q be the set of merged adjacency
lists.
(b) For each list L 2 Q, if L contains more than (2
remove L from Q.
(2) For each merged adjacency list L 2 Q,
(a) if L contains an edge in Half-INPUT, remove L from Q;
(b) detect and remove internal and secondary external edges from L;
(c) if, for all edges hu; vi in L, w(u; v)  tmp-h(L), remove L from Q.
After Procedure Ext M&C is executed, all the remaining merged lists are representing
the core clusters of trees in F j . Moreover, for tree T 2 F j with fewer than 2 i
vertices, Procedure Ext M&C, like Procedure M&C, always retains the merged list L cc
that represents the core cluster of T . L cc is not removed by Step 1(b) because L cc
cannot contain more than (2 edges. In addition, L cc contains all the
light primary external edges of T . In Lemma 10 below, we show that tmp-h(L cc )
is the weight of a heavy internal or external edge of T . Thus, L cc contains edges
with weight less than tmp-h(L cc ) and cannot be removed by Step 2(c).
Lemma 10. tmp-h(L cc ) is equal to the weight of a heavy internal or external
edge of T .
Proof. Among all the lists in Q j 1 that are merged into L cc , let L be the one
Optimal Parallel MST Algorithm  19
with the smallest threshold. That is, tmp-h(L cc denote the tree
in F j 1 represented by L. By R4, h(L) is equal to the weight of a heavy internal
or external edge e of W . Thus e is also a heavy internal or external edge of T .
5.3 Updating Threshold and Retaining only External Edges
After Procedure Ext M&C is executed, every remaining merged list is representing
the core-cluster of a tree in F j . Let L cc be such a list representing a tree T 2 F j . If
contains less than 2 i vertices, all light primary external edges of T appear among
the smallest edges in L cc , and all other edges in L cc are heavy edges. If
T has at least 2 i vertices, no external or internal edges of T are light and all edges
in L cc must be heavy. By the denition of Ext M&C, the number of edges in L cc is
at most (2 bi=2 may exceed the length requirement for Phase j (i.e.,
1). To ensure that L cc satises and R3, we retain only the 2 bi=2 j c 1
smallest edges on L cc . The threshold of L cc , denoted by h(L cc ), is updated to be
the minimum of tmp-h(L cc ) and the weight of the smallest edge truncated.
contains fewer than 2 i vertices or not, every edge truncated
from L cc is heavy. Together with Lemma 10, we can conclude that h(L cc ) is equal
to the weight of a heavy internal or external edge of T , satisfying R4.
Next, we give an observation on L cc and in Lemma 12, we show that R5 is
satised. Denote Z 0 as the core-cluster of T represented by L cc .
Lemma 11. Let e be an external edge of Z 0 . If e is a tree edge of T , then e is
not included in L cc and h(L cc )  w(e).
Proof. Suppose e is included in L cc . Note that e cannot be a full edge with
respect to Q because a full edge and its mate should have been removed in
Step 2(b) in Procedure Ext M&C. Then e is in Half-INPUT and Procedure Ext M&C
should have removed L cc at Step 2(a). This contradicts that L cc is one of the
remaining lists after Procedure Ext M&C is executed. Therefore, e is not included
in L cc .
Next, we show that h(L cc )  w(e). Let W be the subtree of Z 0 such that e
is an external edge of W . Since e is a tree edge, e is a primary external edge of
W . As e is not included in L cc and L cc inherits the adjacency list LW 2
representing W , e is also not included in LW . By R5, h(LW )  w(e). Recall that
Lemma 12. Let e be an external edge of T currently not found in L cc . If (i) e
is primary, or (ii) e is secondary and the mate of e is still included in some other
list L 0 in Q j , then h(L cc )  w(e).
Proof. Let vi be an external edge of T currently not found in L cc ,
satisfying the conditions stated in Lemma 12. Let W be the tree in F j 1 such that
W is a subtree of T and e is an external edge of W . With respect to W , either e
is primary, or e is secondary and the mate of e is included in another list in Q
We consider whether W is included in the core cluster Z 0 of T .
Case 1. W is a subtree of Z 0 . By denition of Z 0 , W must be represented by a list
At the end of Phase j 1, e may or may not appear in LW . If e does not
20  K.W. Chong, Y. Han, and T.W. Lam
a
Z
Fig. 7. Z 0 and Z is connected by a path P in T , and P contains an edge (a; b), which is an
external edge of both Z 0 and W 0 .
appear in LW , then, by R5, h(LW
we have h(L cc )  w(e). Suppose that e is in LW . Then e is passed to L cc when
Procedure Ext M&C starts o. Yet e is currently not in L cc . If e is removed from
L cc within Procedure Ext M&C, this has to take place at Step 2(b), and e is either
an internal edge of T or a secondary external edge removed together with its mate.
This contradicts the assumption about e. Thus, e is removed after Procedure
Ext M&C, i.e., due to truncation. In this case, the way h(L cc ) is updated guarantees
Case 2. W is a subtree of a non-core cluster Z. We show that Z 0 has an external
w(e). Observe that T
contains a path connecting Z 0 and Z, and this path must involve an external edge
ha; bi of Z 0 . By Lemma 11, h(L cc )  w(a; b).
Next we show that w(a; b) < w(e). Let W 0 be the tree in F j 1 such that W 0 is a
subtree of Z 0 and ha; bi is an external edge of W 0 . See Figure 7. Suppose we remove
the edge (a; b) from T , T is partitioned into two subtrees T a and T b , containing the
vertices a and b, respectively. Note that T b contains W , and e is an external edge
of T b . On the other hand, Z 0 is included in T a , and e T is not an external edge of T b .
By Lemma 3, the minimum external edge of T b is hb; ai. Therefore, w(a; b) < w(e).
As a result, h(L cc )  w(a; b) < w(e) and the lemma follows.
Removing remaining internal edges: Note that L cc may still contain some
internal edges of T . This is because Procedure Ext M&C only remove those internal
edges whose mates also appear in L cc . The following lemma shows that every remaining
internal edges in L cc has a weight greater than h(L cc ). Thus by discarding
those edges in L cc with weight greater than h(L cc ), we ensure that only external
edges of T are retained. Of course, no light primary external edge can be removed
by this step.
Lemma 13. For any internal edge e of T that is currently included in L cc ,
Proof. We consider whether is an internal or external edge of Z 0 .
Optimal Parallel MST Algorithm  21
a
Fig. 8. The pair of vertices u and v of e is connected by a path P in T . Every edge on P has
weight smaller than w(e).
Case 1. e is an internal edge of Z 0 . Suppose L cc inherits e from the list
represents a tree W 2 F j 1 and W is a subtree of Z 0 . By
R1, hu; vi is an external edge of W . Then Z 0 includes another tree W 0 2 F j 1 which
contains the vertex v. Denote LW 0 as the list in Q j 1 that represents W 0 . The edge
hv; ui is an external edge of W 0 . But hv; ui does not appear in LW 0 (otherwise,
would have also inherited hv; ui from LW 0 and Procedure Ext M&C should have
removed both hu; vi and hv; ui from L cc at Step 2(b)). By R5, h(LW 0 )  w(u; v).
As
Case 2. e is an external edge of Z 0 . By Lemma 11, e is not a tree edge of T . Let
P be a path on T connecting u and v. See Figure 8. Since T is a subtree of T
G , every
edge on P has weight smaller than w(u; v). On P , we can nd an external edge
ha; bi of Z 0 . By Lemma 11 again, h(L cc )  w(a; b) and hence h(L cc )  w(u; v).
5.4 The complete algorithm
The discussion of Thread i in the previous three sections is summarized in the
following procedure. The time and processor requirement will be analyzed in the
next section.
Thread i
Input:. G; B k , where 1  k  i 1, is available at the end of the kth superstep
Construct Q 0 from G; a 0 0
3 For to blog ic do // Phase j
// denote INPUT as B[a
(1) (a) Edges in INPUT that are full with respect to Q lists in
be the set of merged adjacency lists.
(b) For each list L 2 Q, if L contains at most (2 bi=2
is a part of Lg; otherwise,
remove L from Q.
(2) For each list L 2 Q, // Remove unwanted edges and lists
22  K.W. Chong, Y. Han, and T.W. Lam
(a) if L contains an edge in Half-INPUT, remove L from Q;
(b) detect and remove internal and secondary external edges from L;
(c) if, for all edges hu; vi in L, w(u; v)  tmp-h(L), remove L from Q.
(3) // Truncate each list if necessary and remove remaining internal edges
(a) For each list L 2 Q, if L contains more than 2 bi=2 j c 1 edges, retain the
smallest ones and update h(L) to the minimum of tmp-h(L)
and w(e is the smallest edge just removed from L.
(b) For each edge hu; vi 2 L, if w(u; v)  h(L), remove hu; vi from L.
appears in some list L in Q blog ic ; w(u; v) < h(L)
g.
6. TIME AND PROCESSOR COMPLEXITY
First, we show that the new MST algorithm runs in O(log n) time using (n+m) log n
CREW PRAM processors. Then we illustrate how to modify the algorithm to run
on the EREW PRAM and reduce the processor bound to linear.
Before the threads start to run concurrently, they need an initialization step.
First, each adjacency list of G is sorted in ascending order with respect to the
edge weights. This set of sorted adjacency lists is replicated blog nc times and
each copy is moved to the \local memory" of a thread, which is part of the global
shared memory dedicated to the processors performing the \local" computation of
a thread. The replication takes O(log n) time using a linear number of processors.
Then each thread constructs its own Q 0 in O(1) time. Afterwards, the threads run
concurrently.
As mentioned in Section 3, the computation of a thread is scheduled to run in
a number of phases. Each phase starts and ends at predetermined supersteps. We
need to show that the computation of each phase can be completed within the
allocated time interval. In particular, Phase j of Thread i is scheduled to start at
the (a j +1)th superstep and end at the a j+1 th superstep using
supersteps. The following lemma shows that Phase j of Thread i can
be implemented in c(i=2 j 1 ) time, where c is a constant. By setting the length
of a superstep to a constant c 0 such that c(i=2 j 1 )=c 0   1
Phase j can
complete its computation in at most  1
supersteps. It can be verify that
Lemma 14. Phase j of Thread i can be implemented in O(i=2 using
processors.
Proof. Consider the computation of Phase j of Thread i. Before the merging
of the adjacency list starts, Thread i reads in B[a which may also
be read by many other threads, into the local memory of Thread i. The merging
of adjacency lists in Step 2(a) takes O(1) time. In Step 2(b), testing the
length of a list ( (2 bi=2 can be done by performing pointer jumping in
time. After that, all adjacency lists left have
length at most (2 bi=2 . In the subsequent steps, we make use of standard
parallel algorithmic techniques including list ranking, sorting, and pointer jumping
Optimal Parallel MST Algorithm  23
to process each remaining list. The time used by these techniques is the logarithmic
order of the length of each list (see e.g., JaJa [1992]). Therefore, all the steps of
Phase j can be implemented in c(i=2 using a linear
number of processors.
Corollary 1. The minimum spanning tree of a weighted undirected graph can
be found in O(log n) time using (n +m) log n CREW PRAM processors.
Proof. By Lemma 14, the computation of Phase j of Thread i satises the
predetermined schedule. Therefore, B i can be found at the end of the ith superstep
and B[1; blog nc] are all ready at the end of the blog ncth superstep. That means the
whole algorithm runs in O(log n) time. As Thread i uses at most n+m processors,
(n +m) log n processors su-ce for the whole algorithm.
6.1 Adaptation to EREW PRAM
We illustrate how to modify the algorithm to run on the EREW PRAM model.
Consider Phase j of Thread i. As discussed in the proof of Lemma 1, concurrent
read is used only in accessing the edges of B[a which may also be read
by many other threads at the same time. If B[a have already resided in
the local memory of Thread i, all steps can be implemented on the EREW PRAM.
To avoid using concurrent read, we require each thread to copy its output to
each subsequent thread. By modifying the schedule, each thread can perform this
copying process in a sequential manner. Details are as follows: As shown in the
proof of Lemma 1, Phase j of Thread i can be implemented in c(i=2
where c is a constant. The length of a superstep was set to be c 0 so that Phase j
of Thread i can be completed within
supersteps. Now the length of
each superstep is doubled (i.e., each superstep takes 2c 0 time instead of c 0 ). Then
the computation of Phase j can be deferred to the last half supersteps (i.e., the
last  1
supersteps). In the rst half supersteps of Phase j (i.e., from the
1)th to (a j+1
)th supersteps), no computation is performed.
Thread i is waiting for other threads to store the outputs B a j 1 into the
local memory.
To complete the schedule, we need to show how each Thread k, where k < i,
perform the copying in time. Recall that Thread k completes its computation at
the kth superstep. In the (k to
four threads, namely Thread Each replication
takes using a linear number of processors.
Lemma 15. Consider any Thread i. At the end of the (a
)th super-
step, there is a copy of B[a residing in the local memory of Thread i.
Proof. For k < i, Thread i receives B k at the (k
For Phase j of Thread i, B a j is the last set of edges to be received and it arrives
at the (a
)th superstep, just before the start of
the second half of Phase j.
Han, and T.W. Lam
6.2 Linear processors
In this section we further adapt our MST algorithm to run on a linear number of
processors. We rst show how to reduce the processor requirement to m+ n log n.
Then, for a dense graph with at least n log n edges, the processor requirement is
dominated by m. Finally, we give a simple extra step to handle sparse graphs.
To reduce the processor requirement to m log n, we would like to introduce
some preprocessing to each thread so that each thread can work on only n (instead of
m) edges to compute the required output using n processors. Yet the preprocessing
of each thread still needs to handle m edges and requires m processors. To sidestep
this di-culty, we attempt to share the preprocessing among the threads. Precisely,
the computation is divided into dlog log ne stages. In Stage k, where 1
ne, we perform one single preprocessing, which then allows up to 2 k 1
threads to compute concurrently the edge sets
using processors. The preprocessing itself runs in O(2 k ) supersteps using
processors. Thus, each stage makes use of at most m
and the total number of supersteps over all stages is still O(log n).
Lemma 16. The minimum spanning tree of a weighted undirected graph can be
found in O(log n) time using m+ n log n processors on the EREW PRAM.
Proof. The linear-processor algorithm runs in dloglog ne+1 stages. In Stage 0,
is found by Thread 1. For 1  k  dloglog ne, Stage k is given
and is to compute B[2 Specically, let
Thread 2x for the preprocessing and Threads 1; 2;    ; x for the actual computation
of . Both parts require O(x) supersteps.
The preprocessing is to prepare the initial adjacency lists for each thread. Let F
be the set of trees induced by B[1; x], which is, by denition, a 2 x -forest of G. We
invoke Thread 2x to execute Phase 1 only, computing a set Q 1 of adjacency lists.
By denition, each list in Q 1 has length at most 2 2x=2 representing a
tree T in F and containing all primary external edges of T with base less than 2 2x .
contains su-cient edges for nding not only B 2x but also As
F contains at most n=2 x trees, Q 1 contains a total of at most n edges.
Each list in Q 1 is sorted with respect to the edge weight using O(x) supersteps
and n processors. Then Q 1 is copied into the local memory of Threads 1 to x one by
one in x supersteps using n processors. For 1  i  x, Thread i replaces its initial
set of adjacency lists Q 0 with a new set Q (i)
0 , which is constructed by truncating
each list in Q 1 to include the smallest 2 i 1 edges.
Threads 1 to x are now ready to run concurrently, computing B
respectively. For all 1  i  x, Thread i uses its own Q (i)
0 as the initial set
of adjacency lists and follows its original phase-by-phase schedule to execute the
algorithm stated in Section 5.4. Note that the algorithm of a thread is more versatile
than was stated. When every Thread i starts with Q (i)
0 as input, Thread i will
compute the edge set B x+i (instead of
can be found by Threads 1 to x in x supersteps. Note that Q (i)
0 has at most n
edges, the processors requirement of each thread is n only.
In short, Stage k takes O(x) supersteps using m+x  n  m+n log n processors.
Optimal Parallel MST Algorithm  25
Recall that . The dlog log ne stages altogether run in O(log n) time using
processors.
If the input graph is sparse, i.e., m < n log n, we rst construct a contracted
graph G c of G as follows. We execute Threads 1 to loglog n concurrently to nd
log n], which induces a (log n)-forest B of G. Then, by contracting each tree
in the forest, we obtain a contracted graph G c with at most n= log n vertices.
The contraction takes O(log n) time using m processors. By Lemma 16, the
minimum spanning tree of G c , denoted T
Gc , can be computed in O(log n) time
using m+ (n= log n) log processors. Note that T
Gc and B include exactly
all the edges in T
G . We conclude with the following theorem.
Theorem 1. The minimum spanning tree of an undirected graph can be found
in O(log n) time using a linear number of processors on the EREW PRAM.



--R


New Connectivity and MSF Algorithms for Shu
A Faster Deterministic Algorithm for Minimum Spanning Trees.
A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity

Finding Minimum Spanning Trees on the EREW PRAM.
Finding Connected Components in O(log n loglog n) time on the EREW PRAM.
Parallel Merge Sort.
Finding minimum spanning forests in logarithmic time and linear work using random sampling.
Approximate and Exact Parallel Scheduling with Applications to List
Upper and lower time bounds for parallel random access machines without simultaneous writes.
Fibonacci heaps and their used in improved network optimization algorithms.

An Optimal Randomized Parallel Algorithm for Finding Connected Components in a Graph.
Can a Shared-Memory Model Serve as a Bridging Model for Parallel Computation? <Proceedings>In Proceedings of the 9th ACM Symposium on Parallel Algorithms and Architectures</Proceedings>

A fast and e-cient parallel connected component algorithm
Computing Connected Components on Parallel Computers.

Connected Components in O(lg 3
A Parallel Algorithm for Computing Minimum Spanning Trees.
Random sampling in Graph Optimization Problems.
A randomized linear-time algorithm to nd minimum spanning trees
Fast Connected Components Algorithms for the EREW PRAM.
Parallel Algorithms for Shared-Memory Ma- chines
Parallel Ear Decomposition Search

Undirected Connectivity in O(log 1:5 n) Space.
Finding Minimum Spanning Trees in O(n
A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest
An Optimal Minimum Spanning Tree Algo- rithm
A Randomized Linear Work EREW PRAM Algorithm to Find a Minimum Spanning Forest.
Structures and Network Algorithms.

A Bridging Model For Parallel Computation.

--TR
Data structures and network algorithms
Upper and lower time bounds for parallel random access machines without simultaneous writes
Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
Fibonacci heaps and their uses in improved network optimization algorithms
New connectivity and MSF algorithms for shuffle-exchange network and PRAM
Parallel ear decomposition search (EDS) and <italic>st</>-numbering in graphs
Parallel merge sort
A bridging model for parallel computation
Parallel algorithms for shared-memory machines
Connected components in <italic>O</italic>(lg<supscrpt>3/2</supscrpt>|<italic>V</italic>|) parallel time for the CREW PRAM (extended abstract)
An introduction to parallel algorithms
A parallel algorithm for computing minimum spanning trees
Fast connected components algorithms for the EREW PRAM
A randomized linear-time algorithm to find minimum spanning trees
An efficient and fast parallel-connected component algorithm
Random sampling in graph optimization problems
Finding minimum spanning forests in logarithmic time and linear work using random sampling
Can shared-memory model serve as a bridging model for parallel computation?
<i>SL</i> MYAMPERSANDsube;<i>L</i><sup>4/3</sup>
Finding connected components in <italic>O</italic>(log <italic>n</italic> loglog <italic>n</italic>) time on the EREW PRAM
Optimal randomized EREW PRAM algorithms for finding spanning forests and for other basic graph connectivity problems
A minimum spanning tree algorithm with inverse-Ackermann type complexity
Efficient parallel algorithms for some graph problems
Computing connected components on parallel computers
An Optimal Minimum Spanning Tree Algorithm
A Randomized Linear Work EREW PRAM Algorithm to Find a Minimum Spanning Forest
A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest
A Faster Deterministic Algorithm for Minimum Spanning Trees
Finding Minimum Spanning Trees in O(m alpha(m,n)) Time

--CTR
Tsan-sheng Hsu, Simpler and faster biconnectivity augmentation, Journal of Algorithms, v.45 n.1, p.55-71, October 2002
Stavros D. Nikolopoulos , Leonidas Palios, Parallel algorithms for P
Toshihiro Fujito , Takashi Doi, A 2-approximation NC algorithm for connected vertex cover and tree cover, Information Processing Letters, v.90 n.2, p.59-63,
Vladimir Trifonov, An O(log n log log n) space algorithm for undirected st-connectivity, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
David A. Bader , Guojing Cong, Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs, Journal of Parallel and Distributed Computing, v.66 n.11, p.1366-1378, November 2006
Aaron Windsor, An NC algorithm for finding a maximal acyclic set in a graph, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
Seth Pettie , Vijaya Ramachandran, An optimal minimum spanning tree algorithm, Journal of the ACM (JACM), v.49 n.1, p.16-34, January 2002
minimum spanning trees;parallel algorithms;EREW PRAM;connected components