A new tree matching algorithm

被引：0

作者：

Chen, Y ^{[1
]}

机构：

[1] Univ Winnipeg, Dept Appl Comp Sci, Winnipeg, MB R3B 2E9, Canada

来源：

ISAS/CITSA 2004: INTERNATIONAL CONFERENCE ON CYBERNETICS AND INFORMATION TECHNOLOGIES, SYSTEMS AND APPLICATIONS AND 10TH INTERNATIONAL CONFERENCE ON INFORMATION SYSTEMS ANALYSIS AND SYNTHESIS, VOL 1, PROCEEDINGS: COMMUNICATIONS, INFORMATION TECHNOLOGIES AND COMPUTING | 2004年

关键词：

algorithm; tree matching; trie; disjoined paths;

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Let T and S be rooted, labeled trees. In this paper, we propose a new algorithm to find all nodes in T, at which S matches. The algorithm needs O(vertical bar T vertical bar/l(T) vertical bar center dot vertical bar S vertical bar/l(S)) time, where l(T) and l(S) are the average lengths of the disjoined paths that cover T and S, respectively.

引用

页码：315 / 320

页数：6

共 11 条

[1]

[Anonymous], P 30 FOCS

[2]

[Anonymous], 1973, ART COMPUTER PROGRAM

[3] FASTER TREE PATTERN-MATCHING [J].

DUBINER, M ;

GALIL, Z ;

MAGEN, E .

JOURNAL OF THE ACM, 1994, 41 (02) :205-213

[4]

Ejnioui A, 1995, INTERNATIONAL CONFERENCE ON COMPUTER DESIGN: VLSI IN COMPUTERS & PROCESSORS, PROCEEDINGS, P650, DOI 10.1109/ICCD.1995.528937

[5] PATTERN-MATCHING IN TREES [J].

HOFFMANN, CM ;

ODONNELL, MJ .

JOURNAL OF THE ACM, 1982, 29 (01) :68-95

[6]

Knuth D. E., 1977, SIAM Journal on Computing, V6, P323, DOI 10.1137/0206024

[7] A tree-matching chip [J].

Krishna, V ;

Ranganathan, N ;

Ejnioui, A .

IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, 1999, 7 (02) :277-280

[8]

MEHLHORN K, 1986, GRAPH ALGORITHMS NAD, V2

[9]

RAMESH R, 1990, J SYMBOLIC COMPT, P485

[10] THE TREE-MATCH CHIP [J].

SMITH, DR ;

LIN, JC .

IEEE TRANSACTIONS ON COMPUTERS, 1991, 40 (05) :629-639

← 1 2 →