- ...Data
- This work
was supported by the Air Force Wright Laboratory Aeronautical
Systems Center under DARPA Contract F33615-93-1-1339, by the
Department of the Air Force Rome Laboratories under DARPA Contract
F30602-95-C-0119, and by equipment grants from IBM Corporation,
Digital Equipment Corporation, and Sun Microsystems.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...3#3-hard.
-
By reduction from the ``exact cover by three-sets'' problem.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...cover
- An edge cover of a graph is a subset
K of the edges of the graph such that any node in the graph is
incident on at least one edge in K.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...problem.
- unless 64#64, since we are considering a polynomial-time
reduction.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...50#50.
- As we will see later, although E initially
includes all edges in the complete bipartite graph, the pruning of
edges results in successive reduction of the size of E.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...tree.
- In these preliminary experiments, we used a slightly
different version of the algorithm described in
Section 4.1; we believe that the differences do not
impact the results significantly.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.