Parallel algorithms for planar graph isomorphism and related problems
| Title | Parallel algorithms for planar graph isomorphism and related problems |
| Publication Type | Journal Articles |
| Year of Publication | 1988 |
| Authors | JaJa JF, Kosaraju SR |
| Journal | Circuits and Systems, IEEE Transactions on |
| Volume | 35 |
| Issue | 3 |
| Pagination | 304 - 311 |
| Date Published | 1988/03// |
| ISBN Number | 0098-4094 |
| Keywords | 2D, algorithms;, algorithms;parallel, array;computational, array;CREW-PRAM, coarsest, complexity;graph, components;two-dimensional, COMPUTATION, graph, graph;planar, isomorphism;single-function, model;mesh, models;planar, partitioning, problem;triconnected, processor, theory;parallel |
| Abstract | Parallel algorithms for planar graph isomorphism and several related problems are presented. Two models of parallel computation are considered: the CREW-PRAM model and the two-dimensional array of processors. The results include O( radic;n)-time mesh algorithms for finding a good separating cycle and the triconnected components of a planar graph, and for solving the single-function coarsest partitioning problem |
| DOI | 10.1109/31.1743 |