This thesis proposes an expressive yet efficient declarative framework
for graph matching in constraint programming (CP), and focuses
on efficient algorithms to solve the subgraph isomorphism problem.
The framework is based on graph and map variables, and
specific graph morphism constraints.
This allows to model and solve various graph matching problems,
avoiding the tedious development of dedicated and specific
algorithms.
A specialized filtering algorithm is proposed for the subgraph
isomorphism problem,
which uses the semantic
of the problem as well as the global structure of the two input graphs.
It is shown that it is the state-of-the-art filtering algorithm,
compared to
dedicated algorithms and other CP approaches.
Various search techniques from CP are also extended to the subgraph
isomorphism problem.
An automatic detection and exploitation
of symmetries for the subgraph isomorphism problem is proposed, together
with
a decomposition approach of the search.
The significance of this thesis lies in the fact that, even though the
framework is expressive,
CP can be considered as the state-of-the-art for subgraph isomorphism,
outperforming the dedicated known algorithms on current benchmarks.
| Identifer | oai:union.ndltd.org:BICfB/oai:ucl.ac.be:ETDUCL:BelnUcetd-06262008-145353 |
| Date | 24 June 2008 |
| Creators | Zampelli, Stéphane |
| Publisher | Universite catholique de Louvain |
| Source Sets | Bibliothèque interuniversitaire de la Communauté française de Belgique |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://edoc.bib.ucl.ac.be:81/ETD-db/collection/available/BelnUcetd-06262008-145353/ |
| Rights | unrestricted, J'accepte que le texte de la thèse (ci-après l'oeuvre), sous réserve des parties couvertes par la confidentialité, soit publié dans le recueil électronique des thèses UCL. A cette fin, je donne licence à l'UCL : - le droit de fixer et de reproduire l'oeuvre sur support électronique : logiciel ETD/db - le droit de communiquer l'oeuvre au public Cette licence, gratuite et non exclusive, est valable pour toute la durée de la propriété littéraire et artistique, y compris ses éventuelles prolongations, et pour le monde entier. Je conserve tous les autres droits pour la reproduction et la communication de la thèse, ainsi que le droit de l'utiliser dans de futurs travaux. Je certifie avoir obtenu, conformément à la législation sur le droit d'auteur et aux exigences du droit à l'image, toutes les autorisations nécessaires à la reproduction dans ma thèse d'images, de textes, et/ou de toute oeuvre protégés par le droit d'auteur, et avoir obtenu les autorisations nécessaires à leur communication à des tiers. Au cas où un tiers est titulaire d'un droit de propriété intellectuelle sur tout ou partie de ma thèse, je certifie avoir obtenu son autorisation écrite pour l'exercice des droits mentionnés ci-dessus. |
Page generated in 0.0114 seconds