مرکز منطقه ای اطلاع رساني علوم و فناوري

DocumentCode :

2777503

Title :

Faster tree pattern matching

Author :

Dubiner, Moshe ; Galil, Zvi ; Magen, Edith

Author_Institution :

Dept. of Appl. Math., Tel-Aviv Univ., Israel

fYear :

1990

fDate :

22-24 Oct 1990

Firstpage :

145

Abstract :

Recently, R. Kosaraju (Proc. 30th IEEE Symp. on Foundations of Computer Science, 1989, p.178-83) gave an O(nm^0.75 polylog(m))-step algorithm for tree pattern matching. The authors improve this result by designing a simple O(n√m polylog (m )) algorithm

Keywords :

computational complexity; trees (mathematics); algorithm; ordered labelled trees; tail period pairs; time complexity; tree pattern matching; Algorithm design and analysis; Convolution; Mathematics; Partitioning algorithms; Pattern matching;

fLanguage :

English

Publisher :

ieee

Conference_Titel :

Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on

Conference_Location :

St. Louis, MO

Print_ISBN :

0-8186-2082-X

Type :

conf

DOI :

10.1109/FSCS.1990.89533

Filename :

89533

Link To Document :

https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=2777503