| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4652599 | Electronic Notes in Discrete Mathematics | 2011 | 6 Pages |
Abstract
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 connected graph with structured variables. A variable is an ordered list of vertices that can be replaced with a connected graph by a kind of hyperedge replacements. The graph pattern matching problem (GPMP) is the computational problem to decide whether a given graph pattern matches a given graph. In this paper, we show that GPMP is solvable in polynomial time if for a given graph pattern p, the lengths of all variables of p are 2 and the base graph of p is of bounded treewidth.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
