131st Colloquium of Center for Computational Sciences

131st Colloquium

Title: Subgraph Isomorphism Search: Overview and State-of-the-Art Approaches 

Speaker: John Wang(Associate Professor, Griffith University, Australia)

Date: November 18, 2019 (Mon)

Time: 10:30-11:30

Venue: Center for Computational Sciences, Meeting Room A

Language: English

Given data graph G and query graph P, subgraph isomorphism search is to find subgraphs of G that are isomorphic (i.e., structurally identical) to P.  The problem finds numerous applications, but is computationally  intractable.  Over the years the problem has attracted researchers from different fields, and many algorithms have been proposed.  Roughly, these algorithms can be grouped into three types: those based on Constraint Solving; those based on Depth-First Search and Backtracking; and those  based on Relational Join. In this talk, I will first give a brief overview of  each of these types of algorithms, and then provide the main ideas on the most recent Backtracking algorithms proposed by Database researchers (including our own work).  I will also discuss some variations of problem.

John (Junhu) Wang received his PhD in Computer Science in 2003 from Griffith University, Australia.  He is currently an associate professor at the same university. Before joining Griffith University as an academic staff, he worked as a lecturer at Monash University, Australia from September 2001 to February 2003.  His current research interest is in Graph Query  Processing, Knowledge Representation, Social Network Analysis, and Text Data Analysis.  Previously, he worked on Constraint Reasoning, XML and Tree Pattern Query Processing. More details about Dr Wang can be found at

Coordinator :Toshiyuki Amagasa