Optimal quadratic-time isomorphism of ordered graphs

摘要

In this paper we introduce the concept of ordered graph and ordered graph isomorphism that provides a natural representation of many objects in applications such as computer vision and pattern recognition. While no efficient (polynomial-bound) isomorphism algorithm for general graphs exists today, we show that the ordered graph isomorphism problem can be optimally solved in quadratic time. An experimental evaluation demonstrates the superior performance of the new method. Our ordered graph isomorphism algorithm is simple and can be easily implemented. It is therefore expected to be practically useful in many applications.