Paper Info
Title
An Efficient Pattern Matching Algorithm For Unordered Term Tree Patterns Of Bounded Dimension
Abstract
A term tree pattern is a connected acyclic graph (unrooted unordered tree) pattern with structured variables, which are ordered lists of one or more distinct vertices. A variable of a termtree pattern has a variable label and can be replaced with an arbitrary tree by hyperedge replacement according to the variable label. The dimension of a term tree pattern is the maximum number of vertices in the variables of it. A term tree pattern is said to be linear if each variable label in it occurs exactly once. Let T be a tree and t a linear termtree pattern. In this paper, we study the graph pattern matching problem (GPMP) for T and t, which decides whether or not T is obtained from t by replacing variables in t with some trees. First we show that GPMP for T and t is NP-complete if the dimension of t is greater than or equal to 4. Next we give a polynomial time algorithm for solving GPMP for a tree of bounded degree and a linear term tree pattern of bounded dimension. Finally we show that GPMP for a tree of arbitrary degree and a linear term tree pattern of dimension 2 is solvable in polynomial time.
Year
DOI
Venue
2018
10.1587/transfun.E101.A.1344
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
Keywords
Field
DocType
tree structured pattern, graph pattern matching algorithm, polynomial time algorithm, NP-completeness
String searching algorithm,Discrete mathematics,Mathematics,Bounded function
Journal
Volume
Issue
ISSN
E101A
9
1745-1337
Citations 
PageRank 
References 
0
0.34
0
Authors
5
Name
Order
Citations
PageRank
Takayoshi Shoudai126931.89
Tetsuhiro Miyahara226732.75
Tomoyuki Uchida325535.06
Satoshi Matsumoto4558.66
Yusuke Suzuki515018.82