Ensemble dominantEn théorie des graphes, un ensemble dominant (ou dominating set en anglais) d'un graphe G = ( S, A ) est un sous-ensemble D de l'ensemble S des sommets tel que tout sommet qui n'appartient pas à D possède au moins une arête d'extrémité un sommet de D. Le problème de l'ensemble dominant est de déterminer, étant donné G et un entier naturel k, si G possède un ensemble dominant d'au plus k sommets. Ce problème est NP-complet.
Cutting stock problemIn operations research, the cutting-stock problem is the problem of cutting standard-sized pieces of stock material, such as paper rolls or sheet metal, into pieces of specified sizes while minimizing material wasted. It is an optimization problem in mathematics that arises from applications in industry. In terms of computational complexity, the problem is an NP-hard problem reducible to the knapsack problem. The problem can be formulated as an integer linear programming problem.
Completeness (order theory)In the mathematical area of order theory, completeness properties assert the existence of certain infima or suprema of a given partially ordered set (poset). The most familiar example is the completeness of the real numbers. A special use of the term refers to complete partial orders or complete lattices. However, many other interesting notions of completeness exist. The motivation for considering completeness properties derives from the great importance of suprema (least upper bounds, joins, "") and infima (greatest lower bounds, meets, "") to the theory of partial orders.
