Marc Hellmuth, Wilfried Imrich, Werner Klöckl, Peter Stadler
Paper #: 08-08-033
The problem of recognizing approximate graph products arises in theoretical biology. This paper presents an algorithm that recognizes a large class of approximate graph products. The main part of this contribution is concerned with a new, local prime factorization algorithm that factorizes all strong products on an extensive class of graphs that contains, in particular, all products of triangle-free graphs on at least three vertices. The local approach is linear for graphs with fixed maximal degrees.