This section presents a collection of conservative DRAM algorithms for solving graph problems. The algorithms use two processors per edge of an input graph and require only constant extra space in each processor. Most of the algorithms use treefix computations as subroutines.

We represent each vertex in an undirected graph by a doubly
linked *incidence ring* of processors, one for each edge. Each
element of the incidence ring contains pointers to the next and
previous elements in the ring, and one pointer for a graph edge. For
each edge , the element in the incidence ring for *u*
contains a pointer to an edge element in the incidence ring for *v*,
and vice versa. A directed graph is represented in the same doubly
linked fashion, but the graph edges are labeled with their directions.

We represent trees with arbitrary vertex degrees by an incidence ring
structure as well. If the tree is directed, each ring has a unique
*principal element* that points toward the root. Breaking the
incidence ring before the principal element yields the standard binary-tree
representation of the tree [14, pp. 332-333,].

We now present brief descriptions of the algorithms. The performance
is given in terms of the number of steps on a DRAM when the input
representation has size *n*. We assume the implicit tree contractions
in the algorithms are performed by the randomized Algorithm TC
.
Deterministic bounds can be obtained by multiplying the number of
steps by , where *m* is the number of processors. An
upper bound on the time required in the DRAM model can be obtained by
multiplying the number of steps by the load factor of the input.

**Generalized treefix.** *Perform a treefix operation on a
directed tree with arbitrary vertex degree. The input values
are stored in the principal elements of the tree, which is
where the output values are to be placed. The leaffix value
at a node i whose children have values is
.* Each
nonprincipal element is assigned the identity for its
value. A binary treefix computation performed on the binary tree
representation underlying the tree computes the desired values.

**Tree functions.** *Given a directed tree, compute for each
node the number of descendants, its height, or its depth.* The number
of dependents for each node can be computed by a leaffix computation
with as integer addition and for all nodes. The
height of a node can also be computed by a leaffix computation where
, the identity is , and
for all nodes. The
depth of a node can be computed by a rootfix computation with
as addition and for all nodes except the root which has value
*0*. *Performance: .*

**Rooting an undirected tree.** *Pick a root of a tree with
undirected graph pointers, and orient the graph pointers toward the
root.* Form an ``Eulerian tour'' of the pointers of the representation
[27] by directing each element of the tree to link its
incoming ring pointer with its graph edge directed outward and its
graph edge directed inward with its outgoing ring pointer. Each graph
edge is used twice in the tour, once in each direction, but each ring
pointer is used only once. Use Algorithm LC
to form a
contraction tree of the tour. Choose the root of the contraction tree
to be the root of the tree, and break the tour so that it begins with
the root. Use parallel prefix to number each node according to its
first occurrence in the tour. Use contraction trees to distribute the
smallest value in each incidence ring to the elements of the ring.
Orient each graph edge from the larger value to the smaller. *
Performance: .*

**Rerooting a directed tree.** *Given a directed tree and
another distinguished vertex k, reorient the graph edges of the tree
to point toward k.* The algorithm for rooting a tree can be used by
picking

**Tree-walk numberings of a binary tree.** *Number the nodes of
a binary tree according to the order they would be visited in a
preorder/inorder/postorder tree walk.* For each of the walks, we will
compute , the number of nodes visited before the left subtree of
*k*. Use a leaffix computation to compute the number of the
subtree rooted at *k*. We first compute the preorder numbering. (For
the purposes of these numbering algorithms, we consider the root to be
a left child.) If node *k* is a left child, set . If
node *k* is a right child, set to the size of its sibling
subtree plus *1*. A rootfix computation with *+* yields , which
is the preorder numbering of node *k*. The inorder numbering can be
computed similarly. If node *k* is a left child, set .
If *k* is a right child, set to the size of its sibling subtree
plus *1*. Compute for each node using a rootfix computation
with *+*. The inorder numbering of node *k* is plus
the size of its left subtree plus *1*. The postfix numbering can be computed
by setting if node *k* is a left child, and by setting
to the size of its sibling subtree if *k* is a right child.
After computing using a rootfix computation with *+*, the
postfix numbering of node *k* is plus the sizes of its
two subtrees plus *1*. *Performance: .*

**Prefix and postfix numberings of a directed tree.** *Number
the edges of an arbitrary directed tree according to the order they
are visited in a preorder/postorder tree walk.* The problem reduces to
prefix/postfix numbering on the underlying binary tree representation.
*Performance: .*

**Diameter and center of a tree.** *The diameter is the length
of the longest path in the tree. A center is a vertex v such that
the longest path from v to a leaf is minimal over all vertices in
the tree.* The diameter can be determined by rooting the tree and
using rootfix to find the farthest leaf from the root. Reroot the
tree at this leaf. The distance from the new root to the farthest
leaf is the diameter. (This algorithm is based on an analog algorithm
attributed to J. Wennmacker [6].) A center of the tree can
be determined by finding a median element of the path that realizes
the diameter.

**Centroid of a tree.** *A centroid is a vertex
v such that the largest subtree with v as a leaf is minimal over
all vertices in the tree.* A centroid can be determined by rooting the tree
and computing the size of each subtree. By broadcasting the size

**Separator of a tree.** *A separator [20]
is a partition of the vertices of an n-vertex tree into three sets
A, B, and C, with , , and , such that no edge of the tree goes between a vertex in
A and a vertex in C.* Determine a centroid of the tree. This
vertex is the separator vertex in

**Subexpression evaluation.** *Given a directed tree in which
each leaf has a value and each internal node has an operator from
, compute for each internal node the subexpression
rooted at that node.* A single leaffix-like computation suffices using
the ideas of Brent [2] and Miller and Reif [22].
*Performance: .*

**Minimum-cost spanning forest.** *Given an undirected input
graph and a cost function ,
determine a set of edges such that each vertex in V
is incident on an edge of F, and the sum of the weights of the edges
in F is minimal.* We give a conservative DRAM implementation of
Boruvka's algorithm, also attributed to Sollin
[26, pp. 71-83,]. We assume without loss of generality that
the edge weights are distinct--otherwise, we can assign the weight of
a graph edge

**Connected components.** *Given an undirected input graph
, determine a labeling such that if and only if v and are in the same connected component
of G.* The algorithm is the same as the minimum spanning tree
algorithm, choosing the weight of a graph edge

**Biconnected components.** *Two edges of an undirected graph
are in the same biconnected component if they lie on a
common simple cycle. Determine a labeling such
that if and only if e and are in the same
biconnected component of G.* We give a conservative DRAM
implementation of the biconnectivity algorithm of Tarjan and Vishkin
[27]. We assume that the reader has some familiarity
with that algorithm. Find a (directed) minimum spanning tree
of

**Eulerian cycle.** *An Eulerian cycle of an undirected graph
is a cycle containing each edge in E exactly once.* If any
vertex has odd degree, then no Eulerian cycle exists. Form a set of
disjoint cycles of the pointers of the representation of

Thu Jul 25 19:12:36 EDT 1996