Consider a set of vertices placed on a two-dimensional Euclidean plane with each vertex attached a nonnegative weight . For a given constant , the geometric graph G=(V, E) is defined to have edge set with being the Euclidean distance between vertices i and j. The geometric vertex packing (GVP) problem, which is often called the independent set problem, is defined as selecting the set of pairwise nonadjacent vertices with maximum total weight. The authors limit their attention to the special case that no vertex is within a distance of any other vertices where . A special value of is referred to frequently because of its correspondence to a manufacturing problem in circuit board testing. In this article the authors show that the weighted vertex packing problem for the specially structured geometric graph (SGVP) defined with the above restriction is NP-complete even for the case that all vertex weights are unity and for any . Polynomial procedures have been designed for generating cuts to obtain tight LP upper bounds for the SGVP. Two heuristics with bounded worst-case performance are applied to the LP solution to produce a feasible solution and a lower bound. The authors then use a branch-and-bound procedure to solve the problem to optimality. Computational results on large-scale SGVP problems will be discussed.
