# American Institute of Mathematical Sciences

July  2005, 1(3): 337-343. doi: 10.3934/jimo.2005.1.337

## Algorithms by layer-decomposition for the subgraph recognition problem with attributes

 1 School of Management, Fudan University, Shanghai 200433, China

Received  August 2004 Revised  January 2005 Published  July 2005

Given two planar graphs $G$ and $H$, the subgraph recognition problem (SRP) is concerned with finding all isomorphic subgraphs of $H$ in $G$. Using the idea of layer-decomposition, we develop algorithms for SRP that have computational complexity $O(n(\Delta-1)^{k-1})$, where $\Delta$ is the degree of $G$ and $n, k$ are the orders of $G, H$ respectively.
Citation: Yifan Xu. Algorithms by layer-decomposition for the subgraph recognition problem with attributes. Journal of Industrial & Management Optimization, 2005, 1 (3) : 337-343. doi: 10.3934/jimo.2005.1.337
 [1] Maria Cameron. Computing the asymptotic spectrum for networks representing energy landscapes using the minimum spanning tree. Networks & Heterogeneous Media, 2014, 9 (3) : 383-416. doi: 10.3934/nhm.2014.9.383 [2] Sergei Avdonin, Jonathan Bell. Determining a distributed conductance parameter for a neuronal cable model defined on a tree graph. Inverse Problems & Imaging, 2015, 9 (3) : 645-659. doi: 10.3934/ipi.2015.9.645 [3] Daniel Roggen, Martin Wirz, Gerhard Tröster, Dirk Helbing. Recognition of crowd behavior from mobile sensors with pattern analysis and graph clustering methods. Networks & Heterogeneous Media, 2011, 6 (3) : 521-544. doi: 10.3934/nhm.2011.6.521 [4] Rainer Steinwandt, Adriana Suárez Corona. Attribute-based group key establishment. Advances in Mathematics of Communications, 2010, 4 (3) : 381-398. doi: 10.3934/amc.2010.4.381 [5] Lluís Alsedà, David Juher, Pere Mumbrú. Minimal dynamics for tree maps. Discrete & Continuous Dynamical Systems, 2008, 20 (3) : 511-541. doi: 10.3934/dcds.2008.20.511 [6] Konovenko Nadiia, Lychagin Valentin. Möbius invariants in image recognition. Journal of Geometric Mechanics, 2017, 9 (2) : 191-206. doi: 10.3934/jgm.2017008 [7] Ruben A. Proano, Sheldon H. Jacobson, Janet A. Jokela. A multi-attribute approach for setting pediatric vaccine stockpile levels. Journal of Industrial & Management Optimization, 2010, 6 (4) : 709-727. doi: 10.3934/jimo.2010.6.709 [8] Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68. [9] Oded Schramm. Hyperfinite graph limits. Electronic Research Announcements, 2008, 15: 17-23. doi: 10.3934/era.2008.15.17 [10] J. William Hoffman. Remarks on the zeta function of a graph. Conference Publications, 2003, 2003 (Special) : 413-422. doi: 10.3934/proc.2003.2003.413 [11] John Kieffer and En-hui Yang. Ergodic behavior of graph entropy. Electronic Research Announcements, 1997, 3: 11-16. [12] Roberto De Leo, James A. Yorke. The graph of the logistic map is a tower. Discrete & Continuous Dynamical Systems, 2021, 41 (11) : 5243-5269. doi: 10.3934/dcds.2021075 [13] Boris Muha. A note on the Trace Theorem for domains which are locally subgraph of a Hölder continuous function. Networks & Heterogeneous Media, 2014, 9 (1) : 191-196. doi: 10.3934/nhm.2014.9.191 [14] Erick Limas. An application of minimal spanning trees and hierarchical trees to the study of Latin American exchange rates. Journal of Dynamics & Games, 2019, 6 (2) : 131-148. doi: 10.3934/jdg.2019010 [15] Alba Málaga Sabogal, Serge Troubetzkoy. Minimality of the Ehrenfest wind-tree model. Journal of Modern Dynamics, 2016, 10: 209-228. doi: 10.3934/jmd.2016.10.209 [16] Vincent Delecroix. Divergent trajectories in the periodic wind-tree model. Journal of Modern Dynamics, 2013, 7 (1) : 1-29. doi: 10.3934/jmd.2013.7.1 [17] Miaohua Jiang, Qiang Zhang. A coupled map lattice model of tree dispersion. Discrete & Continuous Dynamical Systems - B, 2008, 9 (1) : 83-101. doi: 10.3934/dcdsb.2008.9.83 [18] Frédéric Bernicot, Bertrand Maury, Delphine Salort. A 2-adic approach of the human respiratory tree. Networks & Heterogeneous Media, 2010, 5 (3) : 405-422. doi: 10.3934/nhm.2010.5.405 [19] Wenxiu Gong, Zuoliang Xu. An alternative tree method for calibration of the local volatility. Journal of Industrial & Management Optimization, 2022, 18 (1) : 137-156. doi: 10.3934/jimo.2020146 [20] Chunqiang Hu, Jiguo Yu, Xiuzhen Cheng, Zhi Tian, Kemal Akkaya, and Limin Sun. CP_ABSC: An attribute-based signcryption scheme to secure multicast communications in smart grids. Mathematical Foundations of Computing, 2018, 1 (1) : 77-100. doi: 10.3934/mfc.2018005

2020 Impact Factor: 1.801