Technical Reports

The ICICS/CS Reading Room

UBC CS TR-87-15 Summary

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