On the Complexity of Recognizing Hamming Graphs and Related Classes of Graphs

详细信息	查看全文 | 推荐本文 |

• 作者：Imrich ; Wilfried ; Klavzar ; Sandi
• 刊名：European Journal of Combinatorics
• 出版年：1996
• 期刊代码：65_01956698
• 类别：mt
• 出版时间：February, 1996
• 卷：17
• 期：2-3
• 页码：209-221
• 文件大小：287 K

摘要

This paper contains a new algorithm that recognizes whether a given graphGis a Hamming graph, i.e. a Cartesian product of complete graphs, inO(m)time andO(n²)space. Heremandndenote the numbers of edges and vertices ofG,respectively. Previously this was only possible inO(mlogn)time.