Efficient Pattern Matching on Graph Patterns of Bounded Treewidth |
| |
| Institution: | 1. Department of Industrial Engineering, Faculty of Engineering, Kharazmi University, Tehran, Iran;2. Department of Mechanical, Automotive, and Materials Engineering, Faculty of Engineering, University of Windsor, Windsor, Canada;3. Ivey Business School, Western University, London, Ontario, Canada;1. Antai College of Economics and Management, Shanghai Jiao Tong University, 1954 Huashan Road, Shanghai, 200030, China;2. Department of Industrial and Management Engineering, Pohang University of Science and Technology, 77 Cheongam-Ro, Nam-Gu, Pohang, 37673, Korea;3. Department of Technology, Operations, and Statistics, Stern School of Business, New York University, 44 West 4th Street, New York, NY 10012, USA;1. Department of Industrial and Management Engineering, Pohang University of Science and Technology, Pohang 37673, South Korea;2. Kellogg School of Management, Northwestern University, Evanston, IL 60208, USA;3. Holy Name Medical Center, Teaneck, NJ 07666, USA;1. University of Duisburg-Essen, Chair of Business Administration and Production Management, Bismarckstr. 90, 47057 Duisburg, Germany;2. University of Seville, School of Engineering, Industrial Management, Camino de los Descubrimientos, s/n, 41092 Sevilla, Spain;3. Fraunhofer Institute for Manufacturing Engineering and Automation IPA, Nobelstrasse 12, 70569 Stuttgart, Germany;1. Institute of Advanced Technology, Nanjing University of Posts and Telecommunications, Nanjing 210023, China;2. LERIA, Université d’Angers, 2 Boulevard Lavoisier, Angers 49045, France;3. Institut Universitaire de France, 1 Rue Descartes, Paris 75231, France;4. Shenzhen Institute of Artificial Intelligence and Robotics for Society, and The Chinese University of Hong Kong, Shenzhen, Shenzhen 518172, China |
| |
| 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. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
