Faster isometric embedding in products of complete graphs (Q1329794)

The authors provide an algorithm to give an isometric embedding of a connected graph into a product of complete graphs or to ascertain that such an embedding does not exist. If the distance matrix of all pairs of a graph with \(m\) edges and \(n\) vertices is part of the input, the algorithm runs in \(O (n^ 2)\) time. Otherwise, the order is \(n^ 2 + D (m, n)\), where this latter term is the time to compute the all-pairs distance matrix of a graph with \(m\) edges and \(n\) vertices. The paper also shows that an \(n\)-vertex subgraph of the cartesian product of \(d\) cliques of size \(a\) cannot have more than \((1/2) (a-1) n \log_ a n\) edges. With this result, the algorithm can decide if a graph \(G\) isn an \(a\)-ary Hamming graph in \(O (n^ 2 \log n)\) time, for fixed \(a\).