On the coding of ordered graphs

作     者：Jiang, X Bunke, H 

作者机构：Univ Bern Dept Comp Sci CH-3012 Bern Switzerland 

出 版 物：《COMPUTING》 (计算)

年 卷 期：1998年第61卷第1期

页      面：23-38页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：graph isomorphism graph coding ordered graph polynomial algorithm 

摘      要：Ordered graph and ordered graph isomorphism provide a natural representation of many objects in applications such as computational geometry, computer vision and pattern recognition. In the present paper we propose a coding procedure for ordered graphs that improves an earlier one based on Eulerian circuits of graphs in terms of both simplicity and computational efficiency. Using our coding approach, we show that the ordered graph isomorphism problem can be optimally solved in quadratic time, although no efficient (polynomial-bound) isomorphism algorithm for general graphs exists today. An experimental evaluation demonstrates the superior performance of the new method.