Stable multi-sets |
| |
Authors: | Arie M C A Koster Adrian Zymolka |
| |
Institution: | Konrad-Zuse-Zentrum für Informationstechnik Berlin, Takustra?e 7, D-14195 Berlin, Germany (e-mail: {koster,zymolka}@zib.de), DE
|
| |
Abstract: | In this paper we introduce a generalization of stable sets: stable multi-sets. A stable multi-set is an assignment of integers
to the vertices of a graph, such that specified bounds on vertices and edges are not exceeded. In case all vertex and edge
bounds equal one, stable multi-sets are equivalent to stable sets.
For the stable multi-set problem, we derive reduction rules and study the associated polytope. We state necessary and sufficient
conditions for the extreme points of the linear relaxation to be integer. These conditions generalize the conditions for the
stable set polytope. Moreover, the classes of odd cycle and clique inequalities for stable sets are generalized to stable
multi-sets and conditions for them to be facet defining are determined.
The study of stable multi-sets is initiated by optimization problems in the field of telecommunication networks. Stable multi-sets
emerge as an important substructure in the design of optical networks.
Received: February 14, 2001/Revised version: September 7, 2001 |
| |
Keywords: | : generalized stable sets polyhedral combinatorics valid inequalities |
本文献已被 SpringerLink 等数据库收录! |
|