Clique and Constraint Models for Maximum Common (Connected) Subgraph Problems
| Autor: | Patrick Prosser, Ciaran McCreesh, Christine Solnon, Samba Ndojh Ndiaye |
|---|---|
| Přispěvatelé: | University of Glasgow, 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), Rueher, Michael, 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 |
| Jazyk: | angličtina |
| Rok vydání: | 2016 |
| Předmět: |
[INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI]
Discrete mathematics 021103 operations research Plate notation Maximum Common Subgraph Clique Subgraph isomorphism problem [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] 0211 other engineering and technologies [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS] 02 engineering and technology Clique (graph theory) Maximum common subgraph isomorphism problem Constraint Programming [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI] Constraint (information theory) Combinatorics Clique problem 0202 electrical engineering electronic engineering information engineering Constraint programming 020201 artificial intelligence & image processing Induced subgraph isomorphism problem Mathematics MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | 22nd International Conference on Principles and Practice of Constraint Programming (CP) 22nd International Conference on Principles and Practice of Constraint Programming (CP), Sep 2016, Toulouse, France. pp.350-368 Lecture Notes in Computer Science ISBN: 9783319449524 CP |
| ISSN: | 0302-9743 |
| Popis: | The maximum common subgraph problem is to find the\ud largest subgraph common to two given graphs. This problem can be\ud solved either by constraint-based search, or by reduction to the maximum\ud clique problem. We evaluate these two models using modern algorithms,\ud and see that the best choice depends mainly upon whether the graphs\ud have labelled edges. We also study a variant of this problem where the\ud subgraph is required to be connected. We introduce a filtering algorithm\ud for this property and show that it may be combined with a restricted\ud branching technique for the constraint-based approach. We show how to\ud implement a similar branching technique in clique-inspired algorithms.\ud Finally, we experimentally compare approaches for the connected version,\ud and see again that the best choice depends on whether graphs have labels |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|