Subtree isomorphism is NC reducible to bipartite perfect matching (Q1115630)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Subtree isomorphism is NC reducible to bipartite perfect matching |
scientific article |
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
