Solving subgraph isomorphism problems with constraint programming

DOI10.1007/s10601-009-9074-3zbMath1213.68473OpenAlexW2046968552MaRDI QIDQ606895

Yves Deville, Christine Solnon, Stéphane Zampelli

Publication date: 19 November 2010

Published in: Constraints (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10601-009-9074-3

zbMATH Keywords

subgraph isomorphismglobal constraintfiltering algorithm

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (7)

A long trip in the charming world of graphs for pattern recognition ⋮ Efficient subgraph matching using topological node feature constraints ⋮ The Glasgow Subgraph Solver: Using Constraint Programming to Tackle Hard Subgraph Isomorphism Problem Variants ⋮ Constraints for generating graphs with imposed and forbidden patterns: an application to molecular graphs ⋮ AllDifferent-based filtering for subgraph isomorphism ⋮ On the subgraph epimorphism problem ⋮ Finding subgraphs with side constraints

Uses Software

• CPGraph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Feedback arc set in bipartite tournaments is NP-complete
• A parametric filtering algorithm for the graph isomorphism problem
• Efficient graph automorphism by vertex partitioning
• Filtering for Subgraph Isomorphism
• CP(Graph): Introducing a Graph Computation Domain in Constraint Programming
• An Algorithm for Subgraph Isomorphism
• A large database of graphs and its use for benchmarking graph isomorphism algorithms
• Constraint satisfaction algorithms for graph pattern matching
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Principles and Practice of Constraint Programming – CP 2003

This page was built for publication: Solving subgraph isomorphism problems with constraint programming