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.
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
MSC:
| 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 |
