𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Efficient bounds for the stable set, vertex cover and set packing problems

✍ Scribed by Dorit S. Hochbaum

Publisher
Elsevier Science
Year
1983
Tongue
English
Weight
802 KB
Volume
6
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Cover inequalities for robust knapsack s
Cover inequalities for robust knapsack setsβ€”Application to the robust bandwidth packing problem
✍ Olivier Klopfenstein; Dritan Nace πŸ“‚ Article πŸ“… 2011 πŸ› John Wiley and Sons 🌐 English βš– 226 KB

## Abstract The robust optimization framework proposed by Bertsimas and Sim accounts for data uncertainty in integer linear programs. This article investigates the polyhedral impacts of this robust model for the 0‐1 knapsack problem. In particular, classical cover cuts are adapted to provide valid

On the nonseparating independent set pro
On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
✍ Shuichi Ueno; Yoji Kajitani; Shin'ya Gotoh πŸ“‚ Article πŸ“… 1988 πŸ› Elsevier Science 🌐 English βš– 350 KB

This paper shows that both the nonseparating independent set problem and feedback set problem can be solved in polynomial time for graphs with no vertex degree exceeding 3 by reducing the problems to the matroid parity problem.