No label defined (Q4378622)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1124594
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1124594 |
Statements
8 July 1998
0 references
optimization
0 references
subset problems
0 references
linear programming
0 references
duality
0 references
0.7932384014129639
0 references
The author shows how many graph-theoretic subset problems such as domination, packing, covering and independence can be formulated as \(\{0,1\}\) programming problems. Expressed as linear programming problems graph-theoretic minimization (respectively, maximization) problems have dual maximization (respectively, minimization) problems which are also discussed. The author also introduces the notion of `complementary' problem using duality. As a consequence of the complementation theorem that is presented, some known results as, for example, Gallai's covering/independence theorem, namely, \(\alpha (G)+ \beta(G)= |V(G)|\), are produced. The chapter concludes with a proposed generalized theory in which vertices are assigned values in some arbitrarily specified set of reals. For the entire collection see [Zbl 0883.00011].
0 references
