A parametric filtering algorithm for the graph isomorphism problem

DOI10.1007/s10601-008-9044-1zbMath1162.05337OpenAlexW2050347117MaRDI QIDQ1020495

Christine Solnon, Sébastien Sorlin

Publication date: 29 May 2009

Published in: Constraints (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10601-008-9044-1

zbMATH Keywords

graph isomorphismglobal constraintvertex labelingfiltering algorithmIDL(d)-filtering

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Solving subgraph isomorphism problems with constraint programming ⋮ On the complexity of submap isomorphism and maximum common submap problems ⋮ Efficient subgraph matching using topological node feature constraints ⋮ Polynomial algorithms for open plane graph and subgraph isomorphisms ⋮ kLog: a language for logical and relational learning with kernels ⋮ Learning an efficient constructive sampler for graphs ⋮ On the subgraph epimorphism problem ⋮ A Polynomial Algorithm for Submap Isomorphism

Uses Software

• CPLEX
• Choco

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Relational consistency algorithms and their application in finding subgraph and graph isomorphisms
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Constraint satisfaction using constraint logic programming
• Filtering for Subgraph Isomorphism
• Automatic Detection of Variable and Value Symmetries
• An Algorithm for Subgraph Isomorphism
• A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• Principles and Practice of Constraint Programming – CP 2003