Parallel algorithms for planar graph isomorphism and related problems

DOI10.1109/31.1743MaRDI QIDQ3801100zbMATH OpenOpenAlexFDO

Authors S. R. Kosaraju, Joseph 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

array of processorscoarsest partitioningCREW-PRAMmodels of parallel computationparallel algorithmsplanar graph isomorphismseparating cycle

Mathematics Subject Classification ID

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

Recommendations

• A Randomized Parallel Algorithm for Planar Graph Isomorphism
• An optimal parallel algorithm for planar cycle separators
• Isomorphism of planar graphs (working paper)
• An efficient parallel algorithm for planarity
• Optimal parallel algorithms on planar graphs

Cited in

(22)

• An external-memory depth-first search algorithm for general grid graphs
• An efficient parallel algorithm for planarity
• A model classifying algorithms as inherently sequential with applications to graph searching
• Finding congruent regions in parallel
• Not all planar digraphs have small cycle separators
• Parallel search algorithms for graphs and trees
• Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs
• An efficient parallel algorithm for the single function coarsest partition problem
• An optimal simple parallel algorithm for testing isomorphism of maximal outerplanar graphs
• An efficient parallel algorithm for finding rectangular duals of plane triangular graphs
• An optimal parallel algorithm for planar cycle separators
• Parallel recognition algorithms for chordal-planar graphs and planar k-trees
• scientific article; zbMATH DE number 4049079 (Why is no real title available?)
• scientific article; zbMATH DE number 4060741 (Why is no real title available?)
• Parallel Tree Contraction Part 2: Further Applications
• A Randomized Parallel Algorithm for Planar Graph Isomorphism
• scientific article; zbMATH DE number 3995071 (Why is no real title available?)
• Parallel algorithms for P4-comparability graphs
• Parallel Algorithm for Solving the Graph Isomorphism Problem
• Improved parallel depth-first search in undirected planar graphs
• Topological recognition of polyhedral objects from multiple views
• Distributed Testing of Graph Isomorphism in the CONGEST Model.

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3801100)