This paper describes the LINK software system, which provides not only a graph editor and graph library, but a computing environment that employs object-oriented Scheme to provide a flexible workbench for algorithm learners and experimenters. Copyright © 2000 John Wiley & Sons, Ltd.

The matrix chain ordering problem is to find the cheapest way to multiply a chain of n matrices, where the matrices are pairwise compatible but of varying dimensions. Here we give several new parallel algorithms including $O(\lg^3 n)$-time and $n/\!\lg n$-processor algorithms for solving the matrix chain ordering problem and for solving an optimal triangulation problem of convex polygons on the common CRCW PRAM model. Next, by using efficient algorithms for computing row minima of totally monotone matrices, this complexity is improved to $O(\lg^2 n)$ time with n processors on the EREW PRAM and to $O(\lg^2 n \lg \lg n)$ time with $n/ \! \lg \lg n$ processors on a common CRCW PRAM\@. A new algorithm for computing the row minima of totally monotone matrices improves our parallel MCOP algorithm to $O(n \lg^{1.5} n)$work and polylog time on a CREW PRAM\@. Optimal log-time algorithms for computing row minima of totally monotone matrices will improve our algorithm and enable it to have the same work as the sequential algorithm of Hu and Shing [SIAM J. Comput., 11 (1982), pp. 362--373; SIAM J. Comput., 13 (1984), pp. 228--251].

It is a fundamental open problem whether polylogarithmic time and a linear number of processors are sufficient for computing the strongly connected components of a directed graph and constructing directed spanning trees for these components. This paper provides the first nontrivial partial solution to the tree problem: for a strongly connected planar directed graph of size n a directed spanning tree rooted at a specified vertex can be computed in $O(\log ^2 n)$ time with ${n / {\log n}}$ processors. This result complements an algorithm by Kao that computes the strongly connected components of a planar directed graph in $O(\log ^3 n)$ time with ${n / {\log n}}$ processors. Both algorithms run on a deterministic parallel random-access machine that permits concurrent reads and concurrent writes in its shared memory and, in case of a write conflict, allows an arbitrary processor to succeed.

We present a general technique for simulating a broad class of T(n)-time and P(n)-processor algorithms on P(n)/T(n) processors using only O(T(n)) time for problems of size n.Surprisingly, this technique is not work conserving; many processors might be idle for long periods of time during the simulation.This generafizes and extends recent work on designing algorithms with optimal processor-time products for the parallel RAM model.These techniques enable us to design optimal processor-time product PRAM algorithms for the problems on planar graphs of maximal independent set, 5-coloring, 7-coloring,connected components, and maximal matching.These algorithms use linear space and from O(log n) to O(log n log* n) time, depending on the model (CRCW or EREW) and the problem.These algorithms are currently the fastest, most processor efficient, and most space efficient for these problems on the PRAM models.

Almost every problem on digraphs requires computing strongly connected components and directed spanning trees in one form or another. It has long been an open problem whether polylog time and linear processors are enough to find the strongly connected components of a digraph and compute directed spanning trees for these components. This paper provides the first non-trivial partial solution to this open problem: For a planar digraph with n vertices, the strongly connected components can be computed in O(log3n) time and O(n) processors. If the graph is strongly connected, a directed spanning tree can be built in O(log2 n) time and O(n) processors. Both algorithms are deterministic and run on a parallel random access machine that allows concurrent reads and concurrent writes in its shared memory.

This paper describes efficient deterministic techniques for breaking symmetry in parallel. These techniques work well on rooted trees and graphs of constant degree or genus. The primary technique allows us to 3-color a rooted tree in $O( \lg^* n )$ time on an EREW PRAM using a linear number of processors. These techniques are used to construct fast linear processor algorithms for several problems, including the problem of $( \Delta + 1)$-coloring constant-degree graphs and 5-coloring planar graphs. Lower bounds for 2-coloring directed lists and for finding maximal independent sets in arbitrary graphs are also proved.

We describe efficient deterministic techniques for breaking symmetry in parallel. The techniques work well on rooted trees and graphs of constant degree or genus. Our primary technique allows us to 3-color a rooted tree in Ο(lg*n) time on an EREW PRAM using a linear number of processors. We apply these techniques to construct fast linear processor algorithms for several problems, including (Δ + 1)-coloring constant-degree graphs, 5-coloring planar graphs, and finding depth-first-search trees in planar graphs. We also prove lower bounds for 2-coloring directed lists and for finding maximal independent sets in arbitrary graphs.