
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

A Polynomial Time Pattern Matching Algorithm on Graph Patterns of Bounded Treewidth
Takayoshi SHOUDAI Takashi YAMADA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E100A
No.9
pp.17641772 Publication Date: 2017/09/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E100.A.1764
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: graph pattern matching, partial ktree pattern, bounded treewidth, hyperedge replacement, polynomial time algorithm,
Full Text: PDF(1.2MB) >>Buy this Article
Summary:
This paper deals with a problem to decide whether a given graph structure appears as a pattern in the structure of a given graph. A graph pattern is a triple p=(V,E,H), where (V,E) is a graph and H is a set of variables, which are ordered lists of vertices in V. A variable can be replaced with an arbitrary connected graph by a kind of hyperedge replacements. A substitution is a collection of such replacements. The graph pattern matching problem (GPMP) is the computational problem to decide whether or not a given graph G is obtained from a given graph pattern p by a substitution. In this paper, we show that GPMP for a graph pattern p and a graph G is solvable in polynomial time if the length of every variable in p is 2, p is of bounded treewidth, and G is connected.

