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]

Lluís Alsedà, David Juher, Pere Mumbrú. Minimal dynamics for tree maps. Discrete & Continuous Dynamical Systems - A, 2008, 20 (3) : 511-541. doi: 10.3934/dcds.2008.20.511

[5]

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

[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]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

Roy H. Goodman. NLS bifurcations on the bowtie combinatorial graph and the dumbbell metric graph. Discrete & Continuous Dynamical Systems - A, 2019, 39 (4) : 2203-2232. doi: 10.3934/dcds.2019093

[19]

Mario Roy, Mariusz Urbański. Random graph directed Markov systems. Discrete & Continuous Dynamical Systems - A, 2011, 30 (1) : 261-298. doi: 10.3934/dcds.2011.30.261

[20]

Dominique Zosso, Braxton Osting. A minimal surface criterion for graph partitioning. Inverse Problems & Imaging, 2016, 10 (4) : 1149-1180. doi: 10.3934/ipi.2016036

2018 Impact Factor: 1.025

Metrics

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

Other articles
by authors

[Back to Top]