An experimental evaluation of refinement techniques for the subgraph isomorphism backtracking algorithms

Open Computer Science

Mihelič Jurij¹  Čibej Uroš¹ 

[1] Faculty of Computer and Information Science, University of Ljubljana, Večna pot 113, Ljubljana, 1000, Slovenia;

关键词: graph;    subgraph isomorphism;    backtracking;    algorithm;    experimental algorithmics;   

DOI  :  10.1515/comp-2020-0149

来源: DOAJ

【 摘 要 】

In this paper, we study a well-known computationally hard problem, called the subgraph isomorphism problem where the goal is for a given pattern and target graphs to determine whether the pattern is a subgraph of the target graph. Numerous algorithms for solving the problem exist in the literature and most of them are based on the backtracking approach. Since straightforward backtracking is usually slow, many algorithmic refinement techniques are used in practical algorithms. The main goal of this paper is to study such refinement techniques and to determine their ability to speed up backtracking algorithms. To do this we use a methodology of experimental algorithmics. We perform an experimental evaluation of the techniques and their combinations and, hence, demonstrate their usefulness in practice.

【 授权许可】

Unknown