Subtree isomorphism is NC reducible to bipartite perfect matching
type: Item
instance of: scholarly article
title: Subtree isomorphism is NC reducible to bipartite perfect matching
zbMATH Open document ID: 0664.68072
DOI: 10.1016/0020-0190(89)90170-1
author: Andrzej Lingas
author: Marek Karpinski
published in: Information Processing Letters
publication date: 1989-01-01T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q05
zbMATH DE Number: 4087045
zbMATH Keywords: bipartite graph
zbMATH Keywords: parallel random access machine
zbMATH Keywords: NC-reducibility
zbMATH Keywords: subtree isomorphism
zbMATH Keywords: perfect matching
MaRDI profile type: Publication
full work available at URL: 0020-0190(89)90170-1
OpenAlex ID: W2045160990
cites work: Q4773298
cites work: A taxonomy of problems with fast parallel algorithms
cites work: Q4198056
cites work: Parallel concepts in graph theory
cites work: Subgraph isomorphism for biconnected outerplanar graphs in cubic time
cites work: A Separator Theorem for Planar Graphs
cites work: Subtree Isomorphism in O(n5/2)
cites work: Matching is as easy as matrix inversion
cites work: An Analysis of a Good Algorithm for the Subtree Problem
cites work: On uniform circuit complexity
cites work: Parallel Algorithms for Depth-First Searches I. Planar Graphs
cites work: Simulation of Parallel Random Access Machines by Circuits
description: scientific article; zbMATH DE number 4087045