Subtree isomorphism is NC reducible to bipartite perfect matching (Q1115630)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Subtree isomorphism is NC reducible to bipartite perfect matching |
scientific article; zbMATH DE number 4087045
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Subtree isomorphism is NC reducible to bipartite perfect matching |
scientific article; zbMATH DE number 4087045 |
Statements
Subtree isomorphism is NC reducible to bipartite perfect matching (English)
0 references
1989
0 references
A simple NC reduction of the problem of subtree isomorphism to that of bipartite perfect matching is presented. The reduction implies the membership of the subtree isomorphism problem in random \(NC^ 3\).
0 references
bipartite graph
0 references
parallel random access machine
0 references
NC-reducibility
0 references
subtree isomorphism
0 references
perfect matching
0 references
