13.3.2.1 Subgraph Isomorphism, Common Subgraphs, Subgraph Matching

Chapter Contents (Back)
Subgraph Isomorphism. Isometric. Structure Matching.

Ullmann, J.R.,
An Algorithm for Subgraph Isomorphism,
JACM(23), No. 1, January 1976, pp. 31-42. Graph Isomorphism. See also Use of Continutiy in Character Recognition, A. BibRef 7601

Ullmann, J.R.,
Associating Parts of Patterns,
InfoControl(9), 1966, pp. 583-601. Abstract formulation of discrete relaxation. BibRef 6600

Ullmann, J.R.[Julian R.],
Bit-vector Algorithms for Binary Constraint Satisfaction and Subgraph Isomorphism,
JEA(15), No. 1, January 2011, Article 1.6.
PDF File. Relaxation. Constraint Satisfaction. Constraint satisfaction. Binary constraints. Relaxation BibRef 1101

Ullmann, J.R.[Julian R.],
Degree Reduction in Labeled Graph Retrieval,
JEA(20), No. 5, May 2015, Article 1.3.
DOI Link 1506
degree reduction employs discrete relaxation within a new conceptual framework. BibRef

Eshera, M.A., Fu, K.S.,
An Image Understanding System Using Attributed Symbolic Representation and Inexact Graph-Matching,
PAMI(8), No. 5, September 1986, pp. 604-618. Generate graphs with labeled arcs and features and match. BibRef 8609

Tsai, W.H., and Fu, K.S.,
Subgraph Error-Correcting Isomorphisms for Syntatic Pattern Recognition,
SMC(13), No. 1, January-February 1983, pp. 48-62. BibRef 8301

Tsai, W.H., and Fu, K.S.,
Error-Correcting Isomorphisms of Attributed Relational Graphs for Pattern Analysis,
SMC(9), No. 12, December 1979, pp. 757-768. Still an O(l^3n^2) method. BibRef 7912

Kasif, S., Kitchen, L., Rosenfeld, A.,
A Hough Transform Technique for Subgraph Isomorphism,
PRL(2), 1983, pp. 83-88. BibRef 8300

Wong, E.K.,
Model Matching in Robot Vision by Subgraph Isomorphism,
PR(25), No. 3, March 1992, pp. 287-303.
WWW Link. BibRef 9203

Shoukry, A., Aboutabl, M.,
Neural-Network Approach for Solving the Maximal Common Subgraph Problem,
SMC-B(26), No. 5, October 1996, pp. 785-790.
IEEE Top Reference. Hopfield network. BibRef 9610

El-Sonbaty, Y.[Yasser], Ismail, M.A.,
A New Algorithm for Subgraph Optimal Isomorphism,
PR(31), No. 2, February 1998, pp. 205-218.
WWW Link. 9802
BibRef
Earlier:
A Graph-Decomposition Algorithm for Graph Optimal Monomorphism,
BMVC97(xx-yy).
HTML Version. 0209
BibRef

Wang, J.T.L., Shapiro, B.A., Shasha, D., Zhang, K., and Currey, K.M.,
An Algorithm for Finding the Largest Approximately Common Substructures of Two Trees,
PAMI(20), No. 8, August 1998, pp. 889-895.
IEEE DOI BibRef 9808

Messmer, B.T.[Bruno T.], Bunke, H.[Horst],
A New Algorithm for Error Tolerant Subgraph Isomorphism Detection,
PAMI(20), No. 5, May 1998, pp. 493-504.
IEEE DOI 9806
BibRef
Earlier:
Fast error-correcting graph isomorphism based on model precompilation,
CIAP97(I: 693-700).
Springer DOI 9709
BibRef
Earlier: A2, A1:
Efficient attributed graph matching and its application to image analysis,
CIAP95(44-55).
Springer DOI 9509
BibRef

Messmer, B.T.[Bruno T.], Bunke, H.[Horst],
A decision tree approach to graph and subgraph isomorphism detection,
PR(32), No. 12, December 1999, pp. 1979-1998.
WWW Link. BibRef 9912

Bunke, H., Shearer, K.,
A Graph Distance Metric Based on the Maximal Common Subgraph,
PRL(19), No. 3-4, March 1998, pp. 255-259. 9807
BibRef

Bunke, H., Kandel, A.,
Mean and maximum common subgraph of two graphs,
PRL(21), No. 2, February 2000, pp. 163-168. 0003
BibRef

Fernández, M.L.[Mirtha-Lina], Valiente, G.[Gabriel],
A graph distance metric combining maximum common subgraph and minimum common supergraph,
PRL(22), No. 6-7, May 2001, pp. 753-758.
Elsevier DOI 0105
BibRef

de Piero, F.W.[Fred W.], Krout, D.[David],
An algorithm using length-r paths to approximate subgraph isomorphism,
PRL(24), No. 1-3, January 2003, pp. 33-46.
Elsevier DOI 0211
BibRef

Ferrer, M.[Miquel], Valveny, E., Serratosa, F.[Francesc],
Median graph: A new exact algorithm using a distance based on the maximum common subgraph,
PRL(30), No. 5, 1 April 2009, pp. 579-588.
Elsevier DOI 0903
Median graph; Maximum common subgraph; Minimum common supergraph; Graph matching BibRef

Ferrer, M., Valveny, E., Serratosa, F.,
Median graphs: A genetic approach based on new theoretical properties,
PR(42), No. 9, September 2009, pp. 2003-2012.
Elsevier DOI 0905
Median graph; Genetic search; Maximum common subgraph; Graph matching; Structural pattern recognition BibRef

Ferrer, M.[Miquel], Serratosa, F.[Francesc], Sanfeliu, A.[Alberto],
Synthesis of Median Spectral Graph,
IbPRIA05(II:139).
Springer DOI 0509
BibRef

Sanromà, G.[Gerard], Alquézar, R.[René], Serratosa, F.[Francesc],
A new graph matching method for point-set correspondence using the EM algorithm and Softassign,
CVIU(116), No. 2, February 2012, pp. 292-304.
Elsevier DOI 1201
BibRef
Earlier: A1, A2, A3:
Smooth Simultaneous Structural Graph Matching and Point-Set Registration,
GbRPR11(142-151).
Springer DOI 1105
BibRef
Earlier: A1, A2, A3:
A Discrete Labelling Approach to Attributed Graph Matching Using SIFT Features,
ICPR10(954-957).
IEEE DOI 1008
BibRef
Earlier: A1, A3, A2:
Shape Learning with Function-Described Graphs,
ICIAR08(xx-yy).
Springer DOI 0806
BibRef
And: A1, A3, A2:
Hybrid Genetic Algorithm and Procrustes Analysis for Enhancing the Matching of Graphs Generated from Shapes,
SSPR08(298-307).
Springer DOI 0812
Correspondence problem; Graph matching; Affine registration; Outlier detection; Expectation maximization; Softassign BibRef

Sanfeliu, A., Serratosa, F., Alquézar, R.,
Clustering of Attributed Graphs and Unsupervised Synthesis of Function-described Graphs,
ICPR00(Vol II: 1022-1025).
IEEE DOI 0009
BibRef

Serratosa, F., Alquézar, R., Sanfeliu, A.,
Efficient Algorithms for Matching Attributed Graphs and Function-described Graphs,
ICPR00(Vol II: 867-872).
IEEE DOI 0009
BibRef

Raveaux, R.[Romain], Burie, J.C.[Jean-Christophe], Ogier, J.M.[Jean-Marc],
A graph matching method and a graph matching distance based on subgraph assignments,
PRL(31), No. 5, 1 April 2010, pp. 394-406.
Elsevier DOI 1002
Graph matching; Graph distance; Bipartite graph matching; Graph based representation BibRef

Raveaux, R.[Romain], Burie, J.C.[Jean-Christophe], Ogier, J.M.[Jean-Marc],
A local evaluation of vectorized documents by means of polygon assignments and matching,
IJDAR(15), No. 1, March 2012, pp. 21-43.
WWW Link. 1203
BibRef

Wang, T.[Tao], Dai, G.J.[Guo-Jun], Xu, D.[De],
A polynomial algorithm for submap isomorphism of general maps,
PRL(32), No. 8, 1 June 2011, pp. 1100-1107.
Elsevier DOI 1101
Graph; Combinatorial map; Isomorphism; Symbol graph; Pattern recognition BibRef

Damiand, G.[Guillaume], Solnon, C.[Christine], de la Higuera, C.[Colin], Janodet, J.C.[Jean-Christophe], Samuel, É.[Émilie],
Polynomial algorithms for subisomorphism of nD open combinatorial maps,
CVIU(115), No. 7, July 2011, pp. 996-1010.
Elsevier DOI 1106
BibRef
Earlier: A1, A3, A4, A5, A2:
A Polynomial Algorithm for Submap Isomorphism: Application to Searching Patterns in Images,
GbRPR09(102-112).
Springer DOI 0905
Open combinatorial maps; Isomorphism and subisomorphism; Pattern detection; 2D and 3D images BibRef

Janodet, J.C.[Jean-Christophe], de la Higuera, C.[Colin],
Computing the Overlaps of Two Maps,
CTIC16(65-76).
Springer DOI 1608
BibRef

Gosselin, S.[Stéphane], Damiand, G.[Guillaume], Solnon, C.[Christine],
Signatures of Combinatorial Maps,
IWCIA09(370-382).
Springer DOI 0911
Canonical representation of n-d map. BibRef

Imada, T.[Tomoki], Nagamochi, H.[Hiroshi],
Indexing All Rooted Subgraphs of a Rooted Graph,
IEICE(E95-D), No. 3, March 2012, pp. 712-721.
WWW Link. 1203
BibRef

Weber, M.[Markus], Liwicki, M.[Marcus], Dengel, A.R.[Andreas R.],
Faster subgraph isomorphism detection by well-founded total order indexing,
PRL(33), No. 15, 1 November 2012, pp. 2011-2019.
Elsevier DOI 1210
BibRef
Earlier:
Indexing with Well-Founded Total Order for Faster Subgraph Isomorphism Detection,
GbRPR11(185-194).
Springer DOI 1105
Graph isomorphism; Subgraph isomorphism; Tree search; Decision tree; Indexing BibRef

Elzinga, C.H.[Cees H.], Wang, H.[Hui],
Kernels for acyclic digraphs,
PRL(33), No. 16, 1 December 2012, pp. 2239-2244.
Elsevier DOI 1210
Pattern recognition; Directed graph; Graph similarity; Graph kernel; Graph minors; Path and cycle in graphs BibRef

Zhang, H.Y.[Hong-Yun], Pedrycz, W.[Witold], Miao, D.Q.[Duo-Qian], Zhong, C.M.[Cai-Ming],
A global structure-based algorithm for detecting the principal graph from complex data,
PR(46), No. 6, June 2013, pp. 1638-1647.
Elsevier DOI 1302
Principal curve; Complex data; Global structure; Principal graph; Vertex-merge step; Improved fitting-smoothing phase BibRef

Raviv, D.[Dan], Kimmel, R.[Ron], Bruckstein, A.M.[Alfred M.],
Graph Isomorphisms and Automorphisms via Spectral Signatures,
PAMI(35), No. 8, 2013, pp. 1985-1993.
IEEE DOI 1307
Complexity theory; Eigenvalues and eigenfunctions; Laplace equations; Graph isomorphism BibRef

Liu, H.R.[Hai-Rong], Yang, X.W.[Xing-Wei], Latecki, L.J.[Longin Jan], Yan, S.C.[Shui-Cheng],
Dense Neighborhoods on Affinity Graph,
IJCV(98), No. 1, May 2012, pp. 65-82.
WWW Link. 1204
On graphs as opposed to images. BibRef

Liu, H.R.[Hai-Rong], Latecki, L.J.[Longin Jan], Yan, S.C.[Shui-Cheng],
Fast Detection of Dense Subgraphs with Iterative Shrinking and Expansion,
PAMI(35), No. 9, 2013, pp. 2131-2142.
IEEE DOI 1307
Algorithm design and analysis BibRef

Liu, H.R.[Hai-Rong], Latecki, L.J.[Longin Jan], Yan, S.C.[Shui-Cheng],
Dense Subgraph Partition of Positive Hypergraphs,
PAMI(37), No. 3, March 2015, pp. 541-554.
IEEE DOI 1502
Clustering algorithms BibRef

Morales-González, A.[Annette], Acosta-Mendoza, N.[Niusvel], Gago-Alonso, A.[Andrés], García-Reyes, E.B.[Edel B.], Medina-Pagola, J.E.[José E.],
A new proposal for graph-based image classification using frequent approximate subgraphs,
PR(47), No. 1, 2014, pp. 169-177.
Elsevier DOI 1310
BibRef
Earlier: A2, A1, A3, A4, A5:
Image Classification Using Frequent Approximate Subgraphs,
CIARP12(292-299).
Springer DOI 1209
Approximate graph mining BibRef

Prado-Romero, M.A.[Mario Alfonso], Gago-Alonso, A.[Andrés],
Community Feature Selection for Anomaly Detection in Attributed Graphs,
CIARP16(109-116).
Springer DOI 1703
BibRef

Acosta-Mendoza, N.[Niusvel], Gago-Alonso, A.[Andrés], Medina-Pagola, J.E.[José E.],
On Speeding up Frequent Approximate Subgraph Mining,
CIARP12(316-323).
Springer DOI 1209
BibRef

Sussman, D.L.[Daniel L.], Tang, M.[Minh], Priebe, C.E.[Carey E.],
Consistent Latent Position Estimation and Vertex Classification for Random Dot Product Graphs,
PAMI(36), No. 1, 2014, pp. 48-57.
IEEE DOI 1312
eigen-decomposition of the adjacency matrix for graphs. Analyze graphs in Encyclopedias. BibRef

Tao, S.Q.[Song-Qiao], Huang, Z.D.[Zheng-Dong], Zuo, B.Q.[Bing-Quan], Peng, Y.P.[Yang-Ping], Kang, W.[Weirui],
Partial retrieval of CAD models based on the gradient flows in Lie group,
PR(45), No. 4, 2012, pp. 1721-1738.
Elsevier DOI 1410
Partial retrieval. ARG created from b-rep. Subgraph matching. BibRef

Dahm, N.[Nicholas], Bunke, H.[Horst], Caelli, T.M.[Terry M.], Gao, Y.S.[Yong-Sheng],
Efficient subgraph matching using topological node feature constraints,
PR(48), No. 2, 2015, pp. 317-330.
Elsevier DOI 1411
BibRef
Earlier:
Topological features and iterative node elimination for speeding up subgraph isomorphism detection,
ICPR12(1164-1167).
WWW Link. 1302
Graph matching BibRef

Dahm, N.[Nicholas], Gao, Y.S.[Yong-Sheng], Caelli, T.M.[Terry M.], Bunke, H.[Horst],
Delaunay-supported edges for image graphs,
ICIP15(1036-1040)
IEEE DOI 1512
computer vision; graph matching BibRef

Solnon, C.[Christine], Damiand, G.[Guillaume], de la Higuera, C.[Colin], Janodet, J.C.[Jean-Christophe],
On the complexity of submap isomorphism and maximum common submap problems,
PR(48), No. 2, 2015, pp. 302-316.
Elsevier DOI 1411
Generalized map BibRef

Flouvat, F.[Frédéric], Soc, J.F.N.V.[Jean-François Nguyen Van], Desmier, E.[Elise], Selmaoui-Folcher, N.[Nazha],
Domain-driven co-location mining,
GeoInfo(19), No. 1, January 2015, pp. 147-183.
Springer DOI 1503
Subsets of features frequently located together. BibRef

Fan, X.H.[Xu-Hui], Cao, L.B.[Long-Bing],
A convergence theorem for graph shift-type algorithms,
PR(48), No. 8, 2015, pp. 2751-2760.
Elsevier DOI 1505
Convergence proof BibRef

Pan, S.R.[Shi-Rui], Wu, J.[Jia], Zhu, X.Q.[Xing-Quan], Long, G.D.[Guo-Dong], Zhang, C.Q.[Cheng-Qi],
Finding the best not the most: regularized loss minimization subgraph selection for graph classification,
PR(48), No. 11, 2015, pp. 3783-3796.
Elsevier DOI 1506
Feature selection BibRef

Wu, J.[Jia], Pan, S.R.[Shi-Rui], Zhu, X.Q.[Xing-Quan], Zhang, P.[Peng], Zhang, C.Q.[Cheng-Qi],
SODE: Self-Adaptive One-Dependence Estimators for classification,
PR(51), No. 1, 2016, pp. 358-377.
Elsevier DOI 1601
Attribute weighting BibRef

Ren, W.[Weiya], Li, G.[Guohui], Tu, D.[Dan],
Graph clustering by congruency approximation,
IET-CV(9), No. 6, 2015, pp. 841-849.
DOI Link 1512
computational complexity BibRef

Girault, B., Goncalves, P., Fleury, E.,
Translation on Graphs: An Isometric Shift Operator,
SPLetters(22), No. 12, December 2015, pp. 2416-2420.
IEEE DOI 1512
graph theory BibRef

Iwata, T., Lloyd, J.R., Ghahramani, Z.,
Unsupervised Many-to-Many Object Matching for Relational Data,
PAMI(38), No. 3, March 2016, pp. 607-617.
IEEE DOI 1602
Automobiles. Groups of nodes in separate networks. Word networks. BibRef

Lu, J.[Jing], Wan, W.G.[Wang-Gen],
Identification of Key Nodes in Microblog Networks,
ETRI(38), No. 1, February 2016, pp. 52-61.
DOI Link 1602
BibRef

Fortnow, L.,
The status of the P versus NP problem,
CACM(52), No. 9, September 2009,
DOI Link 1608
BibRef

Babai, L.,
Graph Isomorphism in Quasipolynomial Time,
arXivCornell University Library, 2015,
WWW Link. 1608
BibRef

Muñoz-Briseño, A.[Alfredo], Lara-Alvarez, G.[Gustavo], Gago-Alonso, A.[Andrés], Hernández-Palancar, J.[José],
A novel geometric graph miner and its applications,
PRL(84), No. 1, 2016, pp. 208-214.
Elsevier DOI 1612
Geometric subgraphs BibRef

Escolano, F.[Francisco], Hancock, E.R.[Edwin R.], Lozano, M.A.[Miguel A.], Curado, M.[Manuel],
The mutual information between graphs,
PRL(87), No. 1, 2017, pp. 12-19.
Elsevier DOI 1703
Graph entropy BibRef


Liu, Y.Z.[Yan-Zhen], Bai, X.[Xiao], Yang, H.C.[Hai-Chuan], Jun, Z.[Zhou], Zhang, Z.H.[Zhi-Hong],
Isometric Mapping Hashing,
GbRPR15(325-334).
Springer DOI 1511
BibRef

Lerouge, J.[Julien], Le Bodic, P.[Pierre], Héroux, P.[Pierre], Adam, S.[Sébastien],
GEM++: A Tool for Solving Substitution-Tolerant Subgraph Isomorphism,
GbRPR15(128-137).
Springer DOI 1511
BibRef

Suh, Y.[Yumin], Adamczewski, K.[Kamil], Lee, K.M.[Kyoung Mu],
Subgraph matching using compactness prior for robust feature correspondence,
CVPR15(5070-5078)
IEEE DOI 1510
BibRef

Nie, W.Z.[Wei-Zhi], Liu, A.A.[An-An], Gao, Z.[Zan], Su, Y.T.[Yu-Ting],
Clique-graph matching by preserving global & local structure,
CVPR15(4503-4510)
IEEE DOI 1510
BibRef

El Sayed, A.[Ahmed], Mahmood, A.[Ausif], Sobh, T.[Tarek],
Unsupervised Sub-graph Selection and Its Application in Face Recognition Techniques,
ICIAR15(247-256).
Springer DOI 1507
BibRef

Acosta-Mendoza, N.[Niusvel], Carrasco-Ochoa, J.A.[Jesús Ariel], Martínez-Trinidad, J.F.[José F.], Gago-Alonso, A.[Andrés], Medina-Pagola, J.E.[José E.],
A New Method Based on Graph Transformation for FAS Mining in Multi-graph Collections,
MCPR15(13-22).
Springer DOI 1506
FAS: frequent approximate subgraph. BibRef

Lu, K.[Kai], Zhang, Y.[Yi], Xu, K.[Kai], Gao, Y.[Yinghui], Wilson, R.C.[Richard C.],
Approximate Maximum Common Sub-graph Isomorphism Based on Discrete-Time Quantum Walk,
ICPR14(1413-1418)
IEEE DOI 1412
Accuracy BibRef

Choi, S.W.[Sun-Wook], Lee, C.H.[Chong Ho], Park, I.K.[In Kyu],
Scene Classification via Hypergraph-Based Semantic Attributes Subnetworks Identification,
ECCV14(VII: 361-376).
Springer DOI 1408
BibRef

Brimkov, V.E.[Valentin E.],
Knapsack Intersection Graphs and Efficient Computation of Their Maximal Cliques,
CompIMAGE14(176-187).
Springer DOI 1407
BibRef

Jiang, Q.R.[Qiang-Rong], Chen, H.J.[Huan-Jun], Liu, B.[Bo],
The Application of Graph Kernels in Face Recognition,
DICTA12(1-7).
IEEE DOI 1303
BibRef

Hou, J.[Jian], Xu, E, Chi, L.[Lei], Xia, Q.[Qi], Qi, N.M.[Nai-Ming],
Dominant set and target clique extraction,
ICPR12(1831-1834).
WWW Link. 1302
BibRef

Villuendas-Rey, Y.[Yenny], Caballero-Mota, Y.[Yailé], García-Lorenzo, M.M.[María Matilde],
Using Rough Sets and Maximum Similarity Graphs for Nearest Prototype Classification,
CIARP12(300-307).
Springer DOI 1209
BibRef

Zhang, B.[Baida], Tang, Y.H.[Yu-Hua], Wu, J.J.[Jun-Jie], Huang, L.Q.[Lin-Qi],
A Unique Vertex Deleting Algorithm for Graph Isomorphism,
ISIDF11(1-4).
IEEE DOI 1111
BibRef

Ozdemir, B.[Bahadir], Aksoy, S.[Selim],
Image Classification Using Subgraph Histogram Representation,
ICPR10(1112-1115).
IEEE DOI 1008
Image representation graphs and bag-of-words. Graph of local patches, histogram of subgraphs. BibRef

Schellewald, C.[Christian],
A Bound for Non-subgraph Isomorphism,
GbRPR07(71-80).
Springer DOI 0706
BibRef

Schellewald, C.[Christian], Schnörr, C.[Christoph],
Probabilistic Subgraph Matching Based on Convex Relaxation,
EMMCVPR05(171-186).
Springer DOI 0601
BibRef

Saxena, T.[Tushar], Tu, P.[Peter], Hartley, R.I.[Richard I.],
Recognizing Objects in Cluttered Images Using Subgraph Isomorphism,
DARPA98(875-882).
PDF File. BibRef 9800

Akinniyi, F.A., and Wong, A.K.C.,
A New Product Graph Based Algorithm for Subgraph Isomorphism,
CVPR83(457-467). BibRef 8300

Chapter on Matching and Recognition Using Volumes, High Level Vision Techniques, Invariants continues in
Social Networks, Creation, Visualization, Use .


Last update:Mar 13, 2017 at 16:25:24