Information Technology Reference
In-Depth Information
edge between every pair of vertices that differ on exactly one bit. A partial cube
G of dimension n is a subgraph of the n -dimensional hypercube with the property
that the distance between two vertices in G is equal to their Hamming distance,
i.e., their distance in Q n . In general, a graph G is said to have an isometric
embedding in another graph H whenever G is a subgraph of H and the distance
between any two vertices in G is equal to their distance in H . Hence partial
cubes are the graphs admitting an isometric embedding in Q n , for some n .The
edges of a partial cube can be partitioned into at most n equivalence classes
called zones , each corresponding to one of the n directions of the edges of Q n
(Fig. 1 ).
We consider the following problem:
Partial Cube Covering: Given a partial cube, find a smallest subset S of its
zones such that every vertex is incident to an edge of one of the zones in S.
n , the problem amounts
to finding a smallest subset I of [ n ] such that for every vertex v of the input
partial cube, there is at least one i
If we refer to the labeling of the vertices by words in
{
0 , 1
}
I such that flipping bit i of the word of v
yields another vertex.
2 Classes of Partial Cubes
The reader is referred to the topics of Ovchinnikov [ 16 ] and Hammack et al. [ 14 ]
for known results on partial cubes. Let us also mention that some other struc-
tures previously defined in the literature are essentially equivalent to partial
cubes. Among them are well-graded families of sets defined by Doignon and
Falmagne [ 7 ], and Media , defined by Eppstein, Falmagne, and Ovchinnikov [ 10 ].
We are interested in giving bounds on the minimum number of zones required
to cover the vertices of a partial cube, but also in the computational complexity
of the problem of finding such a minimum cover. Regarding bounds, it would
have been nice to have a general nontrivial result holding for every partial cube.
Unfortunately, only trivial bounds hold in general.
In one extreme case, the partial cube G =( V,E ) is a star, consisting of one
central vertex connected to
|
V
|−
1 other vertices of degree one. This is indeed
a partial cube in dimension n =
1, every zone of which consists of a single
edge. Since there are n vertices of degree one, all n zones must be chosen to
cover all vertices. In the other extreme case, the partial cube is such that there
exists a single zone covering all vertices. This lower bound is attained by the
hypercube Q n .
Table 1 gives a summary of our results for the various families of partial cubes
that we considered. For each family, we consider upper and lower bounds and
complexity results. We now briefly describe the various families we studied. The
proofs of the new results are in the following sections.
|
V
|−
Search WWH ::




Custom Search