Parallel algorithms for planar graph isomorphism and related problems

TitleParallel algorithms for planar graph isomorphism and related problems
Publication TypeJournal Articles
Year of Publication1988
AuthorsJaJa JF, Kosaraju SR
JournalCircuits and Systems, IEEE Transactions on
Volume35
Issue3
Pagination304 - 311
Date Published1988/03//
ISBN Number0098-4094
Keywords2D, 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

DOI10.1109/31.1743