×

Hypercube embedding of distances with few values. (English) Zbl 0813.05075

Barcelo, Hélène (ed.) et al., Jerusalem combinatorics ’93: an international conference in combinatorics, May 9-17, 1993, Jerusalem, Israel. Providence, RI: American Mathematical Society. Contemp. Math. 178, 179-207 (1994).
The author shows that for positive integers \(x\) and \(y\) such that exactly two of \(x\), \(y\), \(x+ y\) are odd, the problem of testing if a distance \(d\) in \(\{x,y,x+ y\}\) is hypercube embeddable is polynomially solvable. However, it is known that the problem without the restriction on \(d\) is NP-complete.
For the entire collection see [Zbl 0806.00023].

MSC:

05E99 Algebraic combinatorics
05C12 Distance in graphs
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite