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] Alberto Bressan, Sondre Tesdal Galtung. A 2-dimensional shape optimization problem for tree branches. Networks & Heterogeneous Media, 2020  doi: 10.3934/nhm.2020031

2019 Impact Factor: 1.366