scientific article; zbMATH DE number 1124594
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].
- On the algorithmic complexity of twelve covering and independence parameters of graphs
- Linear programming and primal-dual problems in graph theory
- Broadcast domination in graphs
- scientific article; zbMATH DE number 4077457 (Why is no real title available?)
- scientific article; zbMATH DE number 1042581 (Why is no real title available?)
- It is all labeling
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4378622)
