On the complexity of recognizing Hamming graphs and related classes of graphs

摘要: Abstract This paper contains a new algorithm that recognizes whether given graph G is Hamming graph, i.e. Cartesian product of complete graphs, in O(m) time and O(n 2 ) space. Here m n denote the numbers edges vertices G, respectively. Previously this was only possible O(m log n) time. Moreover, we present survey other recognition algorithms for retracts graphs isometric subgraphs graphs. Special emphasis also to bipartite case which these classes are reduced binary median partial