A switching algorithm for the solution of quadratic Boolean equations. (English) Zbl 0461.94015


94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
94-04 Software, source code, etc. for problems pertaining to information and communication theory
68R10 Graph theory (including graph drawing) in computer science
94C15 Applications of graph theory to circuits and networks
Full Text: DOI


[1] Aho, V.A.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1976), Addison-Wesley Reading, MA
[2] Aspvall, B.; Plass, M.F.; Tarjan, R.E., A linear-time algorithm for testing the truth of certain quantified Boolean formulas, Information processing lett., 8, 121-123, (1979) · Zbl 0398.68042
[3] Cook, S., The complexity of theorem proving procedures, Proc. 3rd ACM symposium on theory of computing, 151-158, (1971)
[4] Davis, M.; Putnam, H., A computing procedure for quantification theory, J. ACM, 7, 201-215, (1960) · Zbl 0212.34203
[5] Even, S.; Itai, A.; Shamir, A., On the complexity of timetable and multicommodity flow problems, SIAM J. comput., 5, 691-703, (1976) · Zbl 0358.90021
[6] Gavril, F., Testing for equality between maximum matching and minimum node covering, Information processing lett., 6, 199-202, (1977) · Zbl 0367.05056
[7] Hammer, P.L.; Rudeanu, S., Boolean methods in operation research, (1968), Springer New York · Zbl 0155.28001
[8] Pichat, E., The disengagement algorithm, or a new generalition of the exclusion algorithm, Discrete math., 17, 95-106, (1977) · Zbl 0381.06024
[9] Quine, W.V., A way of simplifying truth functions, Am. math. monthly, 52, 627-631, (1955) · Zbl 0068.24209
[10] Simeone, B., Quadratic zero-uno programming, Boolean functions and graphs, ()
[11] Tison, P., Fondement d’une algèbre des systèmes logiques, Automatisme, 298-303, (1967)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.