Parallel algorithms for planar graph isomorphism and related problems

DOI10.1109/31.1743zbMath0654.68092OpenAlexW2105487688MaRDI QIDQ3801100

S. Rao Kosaraju, Joseph F. Ja'Ja'

Publication date: 1988

Published in: IEEE Transactions on Circuits and Systems (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1903/4509

zbMATH Keywords

parallel algorithmsseparating cycleCREW-PRAMmodels of parallel computationarray of processorsplanar graph isomorphismcoarsest partitioning

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items (10)

An efficient parallel algorithm for the single function coarsest partition problem ⋮ Improved parallel depth-first search in undirected planar graphs ⋮ An optimal parallel algorithm for planar cycle separators ⋮ A model classifying algorithms as inherently sequential with applications to graph searching ⋮ Distributed Testing of Graph Isomorphism in the CONGEST Model. ⋮ Not all planar digraphs have small cycle separators ⋮ Parallel search algorithms for graphs and trees ⋮ Topological recognition of polyhedral objects from multiple views ⋮ An external-memory depth-first search algorithm for general grid graphs ⋮ Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs

This page was built for publication: Parallel algorithms for planar graph isomorphism and related problems