Design pattern-matching algorithms for graphs.

The source page states the original problem together with its recorded qualifications and progress updates as follows.

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

Recorded progress.

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

Recorded update.

Submitted by Bruno Courcelle on 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).