Faster subtree isomorphism

被引：82

作者：

Shamir, R ^{[1
]}

Tsur, D ^{[1
]}

机构：

[1] Tel Aviv Univ, Dept Comp Sci, IL-69978 Tel Aviv, Israel

来源：

JOURNAL OF ALGORITHMS | 1999年 / 33卷 / 02期

关键词：

D O I：

10.1006/jagm.1999.1044

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 [计算机软件与理论];

摘要：

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((k(1.5)/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(k(1.5)n) algorithms of Chung and Matula. We also give a randomized (Las Vegas) O(k(1.376)n)-time algorithm for the decision problem, (C) 1999 Academic Press.

引用

页码：267 / 280

页数：14

共 25 条

[1]

Anderson S., 1984, J MOL GRAPHICS, V2, P8

[2]

Behzad M., 1979, GRAPHS DIGRAPHS

[3]

Randomized O(M(vertical bar V vertical bar)) algorithms for problems in matching theory [J].

Cheriyan, J .

SIAM JOURNAL ON COMPUTING, 1997, 26 (06) :1635-1655

[4]

O(N2.5) TIME ALGORITHMS FOR THE SUBGRAPH HOMEOMORPHISM PROBLEM ON TREES [J].

CHUNG, MJ .

JOURNAL OF ALGORITHMS, 1987, 8 (01) :106-112

[5]

COPPERSMITH D, 1990, J SYMBOLIC COMP, V9, P23

[6]

DESSMARK A, 1996, LECT NOTES COMPUTER, V1136, P501

[7]

Dinits EA, 1970, Soviet Mathematics Doklady, V11, P1277

[8]

Even S., 1979, Graph Algorithms

[9]

FEDER T, 1991, P 23 ANN ACM S THEOR, P123

[10]

Garey M.R., 1979, COMPUTERS INTACTABIL

← 1 2 3 →