When Subgraph Isomorphism is Really Hard, and Why This Matters for Graph Databases
From MaRDI portal
Publication:4639034
DOI10.1613/jair.5768zbMath1440.68192OpenAlexW2795050613MaRDI QIDQ4639034
Patrick Prosser, James Trimble, Christine Solnon, Ciaran McCreesh
Publication date: 2 May 2018
Published in: Journal of Artificial Intelligence Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1613/jair.5768
Database theory (68P15) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items
The Glasgow Subgraph Solver: Using Constraint Programming to Tackle Hard Subgraph Isomorphism Problem Variants, Subgraph matching on temporal graphs, Isomorphisms between random graphs
