scientific article; zbMATH DE number 4064509

MaRDI QIDQ3798258zbMATH OpenFDO

Authors Phillip B. Gibbons, Danny Soroker, Gary L. Miller, Richard Karp

Publication date 1988

zbMATH Keywords

bipartite perfect matchingCREW PRAMparallel algorithmRandomizationsubtree isomorphism problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Subtree isomorphism is in random NC
• Subtree isomorphism is NC reducible to bipartite perfect matching
• Faster Subtree Isomorphism
• A note on the subtree isomorphism for ordered trees and related problems
• A Randomized Parallel Algorithm for Planar Graph Isomorphism

Cited in

(4)

• Subtree isomorphism is NC reducible to bipartite perfect matching
• SUBTREE ISOMORPHISM IS IN DLOG FOR NESTED TREES
• Isomorphism testing of k-trees is in NC, for fixed k
• Subtree isomorphism is in random NC

This page was built for publication:

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