CP(Graph+Map) for Approximate Graph Matching
(2005) 1st International Workshop on Constraint Programming Beyond Finate Integer Domains — Location: Stiges, Spain (1.October.2005)
Files
CPgraph.pdf
Open Access - Adobe PDF
- 225.13 KB
Details
- Authors
- Abstract
- Graph pattern matching is a central application in many fields. In various areas, the structure of the pattern can only be approximated and exact matching is then too accurate. We focus here on approximations declared by the user within the pattern, stating which part could be discarded (optional nodes and arcs), and also allowing machting problems between monomorphism and isomorphism through the defintion of forbidden arcs. In this paper, we show how the integration of two new domains of computation over countable structures, graphs and maps, can be used for modeling and solving approximate graph matching as well as many other matching problems. To achieve this, we introduce map variables where the domain and range can be declared as finite set variables. We describe how such extended map variables can be realized on top of finite domaine and finite set variables. On top of CP(Graph+Map), we propose a monomoprhism constraint suitable for various matching problems. Finally, global constraints, enhancing the pruning of the monomorphism constraint and of the different matching problems are proposed.
- Affiliations
Citations
Deville, Y., Dooms, G., Zampelli, S., & Dupont, P. (2005). CP(Graph+Map) for Approximate Graph Matching. 1st International Workshop on Constraint Programming Beyond Finate Integer Domains, Stiges, Spain. https://hdl.handle.net/2078.5/254110