𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Algorithm for the vertex packing problem

✍ Scribed by Yu. V. Voitishin; E. A. Sharkovskaya

Publisher
Springer US
Year
1992
Tongue
English
Weight
184 KB
Volume
28
Category
Article
ISSN
1573-8337

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On the vertex packing problem
On the vertex packing problem
✍ C. De Simone πŸ“‚ Article πŸ“… 1993 πŸ› Springer Japan 🌐 English βš– 546 KB
The mixed vertex packing problem
The mixed vertex packing problem
✍ Alper AtamtΓΌrk; George L. Nemhauser; Martin W.P. Savelsbergh πŸ“‚ Article πŸ“… 2000 πŸ› Springer-Verlag 🌐 English βš– 121 KB
Vertex packings: Structural properties a
Vertex packings: Structural properties and algorithms
✍ G. L. Nemhauser; L. E. Trotter πŸ“‚ Article πŸ“… 1975 πŸ› Springer-Verlag 🌐 English βš– 843 KB

We consider a binary integer programming formulation (VP) for the weighted vertex packing problem in a simple graph. A sufficient "local" optimality condition for (VP) is given and this result is used to derive relations between (VP) and the linear program (VLP) obtained by deleting the integrality