• DocumentCode
    2264069
  • Title

    Faster subtree isomorphism

  • Author

    Shamir, Ron ; Tsur, Dekel

  • Author_Institution
    Dept. of Comput. Sci., Tel Aviv Univ., Israel
  • fYear
    1997
  • fDate
    17-19 Jun 1997
  • Firstpage
    126
  • Lastpage
    131
  • Abstract
    We study the subtree isomorphism problem: Given trees H and G, find a subtree of G which is isomorphic to H or decide that there is no such subtree. We give an O([k1.8/log k] n) time algorithm for this problem, where k and n are the number of vertices in H and G respectively. This improves over the O(k1.5n) algorithms of Chung (1987) and Matula (1978). We also give a randomized (Las Vegas) O(min(k1.45n, kn1.43))-time algorithm for the decision problem
  • Keywords
    computational complexity; randomised algorithms; trees (mathematics); computation time; decision problem; graph theory; randomized algorithm; subtree isomorphism problem; trees; vertices; Bipartite graph; Computer science; Graph theory; Parallel algorithms; Partitioning algorithms; Polynomials; Tree graphs;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Theory of Computing and Systems, 1997., Proceedings of the Fifth Israeli Symposium on
  • Conference_Location
    Ramat-Gan
  • Print_ISBN
    0-8186-8037-7
  • Type

    conf

  • DOI
    10.1109/ISTCS.1997.595164
  • Filename
    595164
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2264069