zbMATH — the first resource for mathematics

Substitution decomposition for discrete structures and connections with combinatorial optimization. (English) Zbl 0567.90073
Algebraic and combinatorial methods in operations research, Proc. Workshop, Ann. Discrete Math. 19, 257-356 (1984).
[For the entire collection see Zbl 0541.00013.]
The authors have developed a generalized version of the substitution decomposition known for Boolean functions, set systems and relations and their applications. It is shown how a general factorization problem in combinatorial optimization over graphs, project networks, partial orders, etc., naturally leads to this kind of decomposition. A general algebraic model of the decomposition is provided. This paper can be regarded as an important step on the way to an algebraic decomposition theory in discrete mathematics.
Reviewer: P.Sawik

90C10 Integer programming
05C35 Extremal problems in graph theory
49M27 Decomposition methods
05B35 Combinatorial aspects of matroids and geometric lattices
90C35 Programming involving graphs or networks
90B35 Deterministic scheduling theory in operations research