Parallel Algorithms for Planar Graph Isomorphism and Related Problems.

Loading...
Thumbnail Image

Files

TR_86-86.pdf (810.38 KB)
No. of downloads: 783

Publication or External Link

Date

1986

Advisor

Citation

DRUM DOI

Abstract

We present new efficient parallel algorithms for planar graph isomorphism and several related problems. Our main parallel model is the SQRT n x SQRT n mesh of processors, where n is the length of the input. Our results include O(SQRT n) time algorithms for finding a good separating cycle and the triconnected components of a planar graph, and for solving the single function coarsest partitioning problem.

Notes

Rights