Premium
Weighted vertex packing problem for specially structured geometric graphs
Author(s) -
Yu Gang,
Kouvelis Panagiotis,
Luo Songjun
Publication year - 1995
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(199502)42:1<81::aid-nav3220420108>3.0.co;2-x
Subject(s) - combinatorics , mathematics , vertex (graph theory) , euclidean geometry , bounded function , upper and lower bounds , neighbourhood (mathematics) , independent set , discrete mathematics , graph , geometry , mathematical analysis
Consider a set of vertices V = {1, 2,…, n } placed on a two‐dimensional Euclidean plane R 2 with each vertex attached a nonnegative weight w : V → R + | V | . For a given constant d >0, the geometric graph G = ( V, E ) is defined to have edge set E = {( i, j ): d ij ⩽ d } with d ij 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. We limit our attention to the special case that no vertex is within a distance β d of any other vertices where 0 ⩽ β < 1. A special value of β (= 1/2) is referred to frequently because of its correspondence to a manufacturing problem in circuit board testing. In this article we 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. We then use a branch‐and‐bound procedure to solve the problem to optimality. Computational results on large‐scale SGVP problems will be discussed. © 1995 John Wiley & Sons, Inc.