Weighted vertex packing problem for specially structured geometric graphs

Gang Yu, Panagiotis Kouvelis and Songjun Luo

Naval Research Logistics (NRL), 1995, vol. 42, issue 1, 81-102

Abstract: Consider a set of vertices V = {1, 2,…, n} placed on a two‐dimensional Euclidean plane R2 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): dij ⩽ d} with dij 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 ⩽ β

Date: 1995
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/1520-6750(199502)42:13.0.CO;2-X

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navres:v:42:y:1995:i:1:p:81-102

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().