Advertisement
Published in:
2014 | OriginalPaper | Chapter
Search Strategies for Subgraph Isomorphism Algorithms
Authors : Uroš Čibej, Jurij Mihelič
Published in: Applied Algorithms
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Searching for subgraph isomorphisms is an essential problem in pattern matching. Most of the algorithms use a branch-and-bound method to sequentially assign pattern nodes to compatible nodes in the target graph. It is well known that the order in which nodes are assigned, a so-called search strategy, influences drastically the size of the search space. In this article we investigate the impact of various search strategies on the efficiency of two algorithms, the first being the Ullmann’s algorithm and the second one the recently proposed improvement of Ullmann’s algorithm. From the large set of proposed orders we find the most successful ones by thorough testing on a large database of graphs.