Graph Isomorphism and Identification Matrices: Sequential Algorithms

摘要

A number of properties on identification matrices are presented here. For example, we prove that adjacency matrices are identification matrices for all bipartite graphs. We also study the application of the theory of identification matrices to solving the graph isomorphism problem, a famous open problem. We show that, given two graphs represented by two identification matrices with respect to a certain relation, isomorphism can be decided efficiently if at least one matrix satisfies the consecutive 1's property or a relaxed property thereof. Graphs which have identification matrices satisfying the consecutive 1's property include, among others, proper interval graphs and doubly convex bipartite graphs. This work leads to the first efficient isomorphism testing algorithms for certain classes of graphs and more efficient algorithms for some other classes of graphs. The algorithms for some classes of graphs including convex bipartite graphs run in linear time and are optimal.