IDA Dept. of Computer and Information science, Linköping University

IDA Technical Reports: abstract

Generated: Tue, 02 Sep 2014 23:26:56

Lingas, A. and Karpinski, M. (1987). Subtree Isomorphism and Bipartite Perfect Matching are Mutually NC Reducible. Technical Report LiTH-IDA-R-87-09, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),

Abstract: 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. It is also shown that the problem of perfect bipartite matching is NC reducible to that of subtree isomorphism. Finally, it is observed that the latter problem is in NC if the first tree is of valence O(logn).


Goto (at Linköping University): CS Dept TR Overview
<webmaster@ida.liu.se>