Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1985-1989 Copyright 1985-1989 Universität Bonn, Institut für Informatik, Abt. V
856

27.11.2008

Subtree Isomorphism and Bipartite Perfect Matching are Mutually NC-Reducible
Marek Karpinski and Andrzej Lingas
[Download PostScript] [Download PDF]

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 NC3. It is also shown that the problem of perfect bipartite matching is NC1 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(log n).

Last Change: 11/28/08 at 13:19:41
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope