Vertex Packings: Structural Properties and Algorithms.

Abstract

A sufficient local optimality condition is given for the weighted vertex packing problem. It is shown that integer-valued variables in an optimal solution to the linearization of this problem retain those same values in an optimal integer solution to the problem. An algorithm is presented and computational experience is given. (Modified author abstract)

Document Details

Document Type
Technical Report
Publication Date
Apr 01, 1974
Accession Number
AD0779440

Entities

People

  • G. L. Nemhauser
  • L. E. Trotter Jr.

Organizations

  • University of Wisconsin–Madison

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Structural Properties

Fields of Study

  • Mathematics

Readers

  • Operations Research