Constraint satisfaction algorithms for graph pattern matching

Graph pattern matching is a central problem in many application fields. Since it is NP-complete, we cannot expect to find algorithms with a good worst-case performance. However, there is still room for general procedures with a good average performance. In this paper we explore four different solvin...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical structures in computer science 2002-08, Vol.12 (4), p.403-422
Main Authors: LARROSA, JAVIER, VALIENTE, GABRIEL
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Graph pattern matching is a central problem in many application fields. Since it is NP-complete, we cannot expect to find algorithms with a good worst-case performance. However, there is still room for general procedures with a good average performance. In this paper we explore four different solving approaches within the constraint satisfaction framework, and introduce a new algorithm, which we call nRF+. The algorithm is a refinement of really full look ahead that takes advantage of the problem structure in order to enhance the look ahead procedure. We give a formal proof that nRF+ is superior to the other approaches in terms of number of visited nodes. An additional contribution of this paper is the introduction of a new benchmark for testing algorithms in this domain. It is formed by a large set of well-defined graphs of very diverse nature. In this benchmark, we show that nRF+ can efficiently solve a broad range of problems, while still leaving many problem instances unsolved. The use of this challenging benchmark is encouraged for future algorithms evaluation.
ISSN:0960-1295
1469-8072
DOI:10.1017/S0960129501003577