A Comparison of Decomposition Methods for the Maximum Common Subgraph Problem
| Autor: | Christine Solnon, Samba Ndojh Ndiaye, Maël Minot |
|---|---|
| Přispěvatelé: | Geometry Processing and Constrained Optimization (M2DisCo), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), ANR-13-BS02-0002,SoLStiCe,Similarités entre données localement structurées pour la vision par ordinateur(2013), Solnon, Christine, Blanc 2013 - Similarités entre données localement structurées pour la vision par ordinateur - - SoLStiCe2013 - ANR-13-BS02-0002 - Blanc 2013 - VALID |
| Rok vydání: | 2015 |
| Předmět: |
[INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI]
Discrete mathematics Decomposition Speedup Computer science Structure (category theory) Class (philosophy) Common Subgraph [INFO] Computer Science [cs] Maximum common subgraph isomorphism problem Constraint Programming [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] Domain (software engineering) Variable (computer science) Constraint programming [INFO]Computer Science [cs] Decomposition method (constraint satisfaction) Graph Triangulation Algorithm |
| Zdroj: | ICTAI 27th IEEE International Conference on Tools with Artificial Intelligence (ICTAI) 27th IEEE International Conference on Tools with Artificial Intelligence (ICTAI), Nov 2015, Vierti sul Mare, Italy. pp.461-468 |
| DOI: | 10.1109/ictai.2015.75 |
| Popis: | International audience; The maximum common subgraph problem is an NP-hard problem which is very difficult to solve with exact approaches. To speedup the solution process, we may decompose it into independent sub-problems which are solved in parallel. We describe a new decomposition method which exploits the structure of the problem to decompose it. We compare this structural decomposition with domain-based decompositions, which basically split variable domains. Experimental results show us that the structural decomposition leads to better speedups on two classes of instances, and to worse speedups on one class of instances. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|