IEICE TRANSACTIONS on Fundamentals
A Polynomial Time Pattern Matching Algorithm on Graph Patterns of Bounded Treewidth
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.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E100-A No.9 pp.1764-1772
- Publication Date
- 2017/09/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E100.A.1764
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Takayoshi SHOUDAI
Kyushu International University
Takashi YAMADA
Kyushu University
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Takayoshi SHOUDAI, Takashi YAMADA, "A Polynomial Time Pattern Matching Algorithm on Graph Patterns of Bounded Treewidth" in IEICE TRANSACTIONS on Fundamentals,
vol. E100-A, no. 9, pp. 1764-1772, September 2017, doi: 10.1587/transfun.E100.A.1764.
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 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E100.A.1764/_p
Copy
@ARTICLE{e100-a_9_1764,
author={Takayoshi SHOUDAI, Takashi YAMADA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Polynomial Time Pattern Matching Algorithm on Graph Patterns of Bounded Treewidth},
year={2017},
volume={E100-A},
number={9},
pages={1764-1772},
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 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.},
keywords={},
doi={10.1587/transfun.E100.A.1764},
ISSN={1745-1337},
month={September},}
Copy
TY - JOUR
TI - A Polynomial Time Pattern Matching Algorithm on Graph Patterns of Bounded Treewidth
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1764
EP - 1772
AU - Takayoshi SHOUDAI
AU - Takashi YAMADA
PY - 2017
DO - 10.1587/transfun.E100.A.1764
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E100-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2017
AB - 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.
ER -
English
