An Algorithm for Maximum Common Subgraph of Planar Triangulation Graphs

1. Conte, D., Foggia, P., Sansone, C., Vento, M.: Thirty Years of Graph Matching in Pattern Recognition. International Journal of Pattern Recognition and Aritificial Intelligence 18(3), 265–298 (2004)

   Article  Google Scholar 

2. Bunke, H., Shearer, K.: A Graph Distance Metric Based on the Maximal Common Subgraph. Pattern Recognition Letters 19(3), 255–259 (1998)

   Article  MATH  Google Scholar 

3. Shearer, K., Bunke, H., Venkatesh, S.: Video Indexing and Similarity Retrieval by Largest Common Subgraph Detection Using Decision Trees. Pattern Recognition 34(5), 1075–1091 (2001)

   Article  MATH  Google Scholar 

4. Schenker, A., Last, M., Bunke, H., Kandel, A.: Classification of Web Documents Using Graph Matching. International Journal of Pattern Recognition and Artificial Intelligence 18(03), 475–496 (2004)

   Article  Google Scholar 

5. Dobkin, D., Friedman, S., Supowit, K.: Delaunay Graphs Are Almost as Good as Complete Graphs. Discrete and Computational Geometry 5(4), 399–407 (1990)

   MathSciNet  MATH  Google Scholar 

6. Berg, M., Cheong, O., Kreveld, M., Overmars, M.: Computational geometry: algorithms and applications. Springer (2008)

   Google Scholar 

7. Finch, A., Wilson, R., Hancock, E.: Matching Delaunay Graphs. Pattern Recognition 30(1), 123–140 (1997)

   Article  MATH  Google Scholar 

8. Shin, D., Tjahjadi, T.: Similarity Invariant Delaunay Graph Matching. In: da Vitoria Lobo, N., Kasparis, T., Roli, F., Kwok, J.T., Georgiopoulos, M., Anagnostopoulos, G.C., Loog, M. (eds.) SSPR & SPR 2008. LNCS, vol. 5342, pp. 25–34. Springer, Heidelberg (2008)

   Google Scholar 

9. Matouěk, J., Thomas, R.: On the Complexity of Finding Iso-and other morphisms for Partial k-trees. Discrete Mathematics 108(1), 343–364 (1992)

   Article  MathSciNet  Google Scholar 

10. McGregor, J.: Backtrack Search Algorithms and the Maximal Common Subgraph Problem. Software Practice and Experience 12(1), 23–34 (1982)

    Article  MATH  Google Scholar 

11. Levi, G.: A Note on the Derivation of Maximal Common Subgraphs of Two Directed or Undirected Graphs. Calcolo 9(4), 341–352 (1972)

    Article  MathSciNet  Google Scholar 

12. Koch, I.: Enumerating All Connected Maximal Common Subgraphs in Two Graphs. Theoretical Computer Science 250(1), 1–30 (2001)

    Article  MathSciNet  MATH  Google Scholar 

13. Bunke, H., Foggia, P., Guidobaldi, C., Sansone, C., Vento, M.: A Comparison of Algorithms for Maximum Common Subgraph on Randomly Connected Graphs. In: Caelli, T.M., Amin, A., Duin, R.P.W., Kamel, M.S., de Ridder, D. (eds.) SSPR & SPR 2002. LNCS, vol. 2396, pp. 123–132. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

14. Conte, D., Foggia, P., Vento, M.: Challenging Complexity of Maximum Common Subgraph Detection Algorithms: A Performance Analysis of Three Algorithms on a Wide Database of Graphs. Journal of Graph Algorithms and Applications 11(1), 99–143 (2007)

    Article  MathSciNet  MATH  Google Scholar 

15. Raymond, J., Willett, P.: Maximum Common Subgraph Isomorphism Algorithms for the Matching of Chemical Structures. Journal of Computer-Aided Molecular Design 16(7), 521–533 (2002)

    Article  Google Scholar 

16. Bern, M., Eppstein, D.: Mesh Generation And Optimal Triangulation. Computing in Euclidean Geometry 1, 23–90 (1992)

    Article  MathSciNet  Google Scholar 

17. Lladós, J., Martí, E., Villanueva, J.: Symbol Recognition by Error-Tolerant Subgraph Matching between Region Adjacency Graphs. IEEE Trans. Pattern Analysis and Machine Intelligence 23(10), 1137–1143 (2001)

    Article  Google Scholar 

18. Konc, J., Janezic, D.: An Improved Branch and Bound Algorithm for the Maximum Clique Problem. Communications in Mathematical and in Computer Chemistry/MATCH 58(3), 569–590 (2007)

    MathSciNet  Google Scholar 

19. Pelillo, M., Torsello, A.: Payoff-Monotonic Game Dynamics and the Maximum Clique Problem. Neural Computation 18(5), 1215–1258 (2006)

    Article  MathSciNet  MATH  Google Scholar 

Download references