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

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.


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


Zbl 0556.00015