A partial cube is a graph having an isometric embedding in a?hypercube. Partial cubes are characterized by a natural equivalence?relation on the edges, whose classes are called zones. The?number of zones determines the minimal dimension of a hypercube?in which the graph can be embedded. We consider the problem of?covering the vertices of a partial cube with the minimum number of?zones. The problem admits several special cases, among which are the following:
展开▼
