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

Petreschi, Rossella; Simeone, Bruno

Inf. Process. Lett. 11, 193-198 (1980).

MSC:

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

Keywords:

algorithms on graphs

References:

[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)