Symmetric complementation. (English) Zbl 0632.68062

Reif, John H.

J. Assoc. Comput. Mach. 31, 401-421 (1984).

This paper introduces a new class of games called symmetric complementing games. These games are interesting since their related complexity classes include many well-known graph problems: Finding minimum spanning forests; k-connectivity and k-blocks; and recognition of chordal graphs, comparability graphs, interval graphs, split graphs, permutation graphs, and constant valence planar graphs. For these problems probabilistic sequential algorithms requiring simultaneously logarithmic space and polynomial time are given. Furthermore, probabilistic parallelism algorithms requiring simultaneously logarithmic time and a polynomial number of processors are also given.

MSC:

68R10	Graph theory (including graph drawing) in computer science
68Q25	Analysis of algorithms and problem complexity
91A80	Applications of game theory

Keywords:

symmetric complementing games; complexity classes; graph problems; probabilistic sequential algorithms; logarithmic space; polynomial time; probabilistic parallelism algorithms; logarithmic time; polynomial number of processors