User menu

Solving subgraph isomorphism problems with constraint programming

Bibliographic reference Zampelli, Stephane ; Deville, Yves ; Solnon, Christine. Solving subgraph isomorphism problems with constraint programming. In: Constraints : an international journal, Vol. 15, no. 3, p. 327-353 (2010)
Permanent URL http://hdl.handle.net/2078.1/33811
  1. Barabasi, A.-L. (2003). Linked: How everything is connected to everything else and what it means. New York: Plume.
  2. Bessière, C., & Van Hentenryck, P. (2003). To be or not to be . . . a global constraint. In Proceedings of the 9th international conference on principles and practice of constraint programming (CP). LNCS (Vol. 2833, pp. 789–794). New York: Springer.
  3. Conte, D., Foggia, P., Sansone, C., & Vento, M. (2004). Thirty years of graph matching in pattern recognition. IJPRAI, 18(3), 265–298.
  4. Cordella, L., Foggia, P., Sansone, C., Tortella, F., & Vento, M. (1998). Graph matching: A fast algorithm and its evaluation. In ICPR ’98: Proceedings of the 14th international conference on pattern recognition (Vol. 2, p. 1582). Washington, DC: IEEE Computer Society.
  5. Cordella, L., Foggia, P., Sansone, C., & Vento, M. (2001). An improved algorithm for matching large graphs. In 3rd IAPR-TC15 workshop on graph-based representations in pattern recognition (pp. 149–159). Cuen.
  6. Cordella, L. P., Foggia, P., Sansone, C., & Vento, M. (1999). Performance evaluation of the vf graph matching algorithm. In ICIAP ’99: Proceedings of the 10th international conference on image analysis and processing (p. 1172). Washington, DC: IEEE Computer Society.
  7. Cormen, T. H., Stein, C., Rivest, R. L., & Leiserson, C. E. (2001). Introduction to algorithms. New York: McGraw-Hill Higher Education.
  8. Darga, P. T., Liffiton, M. H., Sakallah, K. A., & Markov, I. L. (2004). Exploiting structure in symmetry detection for cnf. In Proc. Design Automation Conference (DAC) (pp. 530–534). Piscataway: IEEE/ACM.
  9. Deville, Y., Dooms, G., Zampelli, S., & Dupont, P. (2005). Cp(graph+map) for approximate graph matching. In 1st international workshop on constraint programming beyond finite integer domains, CP2005 (pp. 33–48).
  10. Dooms, G., Deville, Y., & Dupont, P. (2005). Cp(graph): Introducing a graph computation domain in constraint programming. In Principles and practice of constraint programming. Lecture Notes in Computer Science (Vol. 3709, pp. 211–225).
  11. Foggia, P., Sansone, C., & Vento, M.: A database of graphs for isomorphism and sub-graph isomorphism benchmarking. CoRR cs.PL/0105015.
  12. Fowler, G., Haralick, R., Gray, F. G., Feustel, C., & Grinstead, C. (1983). Efficient graph automorphism by vertex partitioning. Artificial Intelligence, 21, 245–269.
  13. Garey, M., & Johnson, D. (1979). Computers and intractability. New York: Freeman.
  14. Grochow, J. A., & Kellis, M. (2007). Network motif discovery using subgraph enumeration and symmetry-breaking. In T. P. Speed, & H. Huang (Eds.), RECOMB. Lecture Notes in Computer Science (Vol. 4453, pp. 92–106). New York: Springer.
  15. Guo, J., Hueffner, F., & Moser, H. (2007). Feedback arc set in bipartite tournaments is np-complete. Information Processing Letters, 102(2–3), 62–65.
  16. Hopcroft, J. E., & Karp, R. M. (1973). An $\text{n}^{\mbox{5/2}}$ algorithm for maximum matchings in bipartite graphs. SIAM Journal on Computing, 2(4), 225–231.
  17. Larrosa, J., & Valiente, G. (2002). Constraint satisfaction algorithms for graph pattern matching, Mathematical. Structures in Computer Science, 12(4), 403–422.
  18. McKay, B. D. (1981). Practical graph isomorphism. Congressus Numerantium, 30, 45–87.
  19. Régin, J. (1995). Développement d’outils algorithmiques pour l’intelligence artificielle. Application à la chimie organique, Ph.D. thesis.
  20. Regin, J.-C. (1994). A filtering algorithm for constraints of difference in CSPs. In Proc. 12th conf. American assoc. artificial intelligence. Amer. assoc. artificial intelligence (Vol. 1, pp. 362–367).
  21. Rudolf, M. (1998). Utilizing constraint satisfaction techniques for efficient graph pattern matching. In Theory and application of graph transformations. Lecture Notes in Computer Science (No. 1764, pp. 238–252). New York: Springer.
  22. Sorlin Sébastien, Solnon Christine, A Global Constraint for Graph Isomorphism Problems, Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (2004) ISBN:9783540218364 p.287-301, 10.1007/978-3-540-24664-0_20
  23. Sorlin, S., & Solnon, C. (2006). A new filtering algorithm for the graph isomorphism problem. In 3rd International workshop on constraint propagation and implementation. CP2006.
  24. Sorlin, S., & Solnon, C. (2008). A parametric filtering algorithm for the graph isomorphism problem. Constraints, 13(4), 518–537.
  25. Ullmann, J. R. (1976). An algorithm for subgraph isomorphism. Journal of the ACM, 23(1), 31–42.
  26. Valiente Gabriel, Algorithms on Trees and Graphs, ISBN:9783642078095, 10.1007/978-3-662-04921-1
  27. Zampelli, S. (2008). A constraint programming approcah to subgraph isomorphism. Ph.D. thesis, UCLouvain, Department of Computing Science & Engineering.
  28. Zampelli, S., Deville, Y., & Dupont, P. (2005). Approximate constrained subgraph matching. In Principles and practice of constraint programming. Lecture notes in computer science (Vol. 3709, pp. 832–836).
  29. Zampelli, S., Deville, Y., Solnon, C., Sorlin, S., & Dupont, P. (2007). Filtering for subgraph isomorphism. In Proc. 13th conf. of principles and practice of constraint programming. Lecture notes in computer science (pp. 728–742). New York: Springer.