Laurent, Monique 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]. Reviewer: Liu Yanpei (Beijing) Cited in 2 Documents MSC: 05E99 Algebraic combinatorics 05C12 Distance in graphs 68R10 Graph theory (including graph drawing) in computer science Keywords:embedding; distance; hypercube; polynomially solvable; NP-complete PDFBibTeX XMLCite \textit{M. Laurent}, Contemp. Math. 178, 179--207 (1994; Zbl 0813.05075)