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]

Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68.

[2]

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

[3]

Gioconda Moscariello, Antonia Passarelli di Napoli, Carlo Sbordone. Planar ACL-homeomorphisms : Critical points of their components. Communications on Pure & Applied Analysis, 2010, 9 (5) : 1391-1397. doi: 10.3934/cpaa.2010.9.1391

[4]

M. R. S. Kulenović, J. Marcotte, O. Merino. Properties of basins of attraction for planar discrete cooperative maps. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2721-2737. doi: 10.3934/dcdsb.2020202

[5]

Francisco Braun, Jaume Llibre, Ana Cristina Mereu. Isochronicity for trivial quintic and septic planar polynomial Hamiltonian systems. Discrete & Continuous Dynamical Systems - A, 2016, 36 (10) : 5245-5255. doi: 10.3934/dcds.2016029

[6]

Rongchang Liu, Jiangyuan Li, Duokui Yan. New periodic orbits in the planar equal-mass three-body problem. Discrete & Continuous Dynamical Systems - A, 2018, 38 (4) : 2187-2206. doi: 10.3934/dcds.2018090

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (36)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]