On the complexity of recognizing Hamming graphs and related classes of graphs (Q1911841)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the complexity of recognizing Hamming graphs and related classes of graphs |
scientific article |
Statements
On the complexity of recognizing Hamming graphs and related classes of graphs (English)
0 references
3 July 1996
0 references
The authors survey recognition algorithms for Hamming graphs (i.e. Cartesian products of complete graphs), retracts of Hamming graphs and isometric subgraphs of Hamming graphs. The paper also contains a new algorithm that recognizes whether a given graph \(G= (V, E)\) is a Hamming graph in \(O(|E|)\) time and \(O(|V|^2)\) space.
0 references
complexity
0 references
recognition algorithms
0 references
Hamming graphs
0 references
