# The ICICS/CS Reading Room

## UBC CS TR-87-15 Summary

- No on-line copy of this technical report is available.

- A Parallel Algorithm for Finding Maximal Independent Sets in Planar Graphs, June 1987 Norm Dadoun and David G. Kirkpatrick
The problem of constructing parallel algorithms for finding Maximal Independent
Sets in graphs has received considerable attention. In the case that the given graph is
planar, the simple efficient parallel algorithm described here may be employed. The
method relies on an efficient parallel algorithm for constructing large independent sets in
bounded degree graphs. This is accomplished by a simple reduction to the same problem
for lists.

Using a linear number of EREW processors, the algorithm identifies a maximal
independent set in an arbitrary planar graph in O$(\log n \log^{*} n)$ parallel time. A
randomized version of the algorithm runs in O$(\log n)$ expected parallel time.

If you have any questions or comments regarding this page please send mail to
help@cs.ubc.ca.