ABSTRACT

In this chapter we show that hypercubes can be recognized in linear time. Deciding whether a given graph is an isometric subgraph of a hypercube is more difficult. We present three algorithms for the solution of this problem: a straightforward one of complexity O(m2), which relies on Theorem 11.8 (iii); a more refined one of complexity O(mn); and one of complexity O(n2), which uses a different computational paradigm.