[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.

Remark

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).

References

[BGT91]

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]