[Submit a comment] [RTALooP home] [Index] [Previous] [Next] [Postscript] [PDF] [BibTeX Source] [LaTeX Source]

Problem #71

Originator: Jean-Claude Raoult
Date: June 1993

Summary: Design pattern-matching algorithms for graphs.

There are good algorithms for pattern-matching for words and trees, but not yet for graphs.


An algorithm for finding the rules of a graph grammar that are applicable to a graph has been given in [BGT91].

Comment sent by Bruno Courcelle

Date: Mon, 31 Jan 2005 10:20:21 +0100

Many types of graph embeddings exist. Thus pattern-matching is not uniquely defined. However, the difficulty of graph isomorphism indicates there cannot exist general algorithms. There may exist in particular cases (bounded degree, for other constraints).


Horst Bunke, T. Glauser, and T.-H. Tran. An efficient implementation of graph grammars based on the RETE-matching algorithm. In H. Ehrig, H.-J. Kreowski, and G. Rozenberg, editors, Graph Grammars and Their Application to Computer Science, volume 532 of Lecture Notes in Computer Science, pages 174–189, 1991.

[Submit a comment] [RTALooP home] [Index] [Previous] [Next] [Postscript] [PDF] [BibTeX Source] [LaTeX Source]