Consistency of quadratic Boolean equations and the König-Egerváry property for graphs. (English) Zbl 0648.05046

Simeone, Bruno

Analysis and design of algorithms for combinatorial problems, Ann. Discrete Math. 25, 281-290 (1985).

[For the entire collection see Zbl 0556.00015.]
The purpose of the present note is to point out the close connection between the consistency of quadratic Boolean equations and the maximum matching-minimum covering equality in graphs. Some of the results can be extended to arbitrary Boolean equations and to hypergraphs.

MSC:

05C70

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Keywords:

quadratic Boolean equations; maximum matching-minimum covering; graphs

Citations:

Zbl 0556.00015