Symmetric Complementation
Publication
, Journal Article
Reif, JH
Published in: Journal of the ACM (JACM)
March 30, 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 mlmmum spanning forests; k-connectiwty and k-blocks; and recognition of chordal graphs, comparabdity graphs, interval graphs, spht graphs, permutation graphs, and constant valence planar graphs. For these problems probabihstlc sequential algorithms requiring simultaneously logarithmic space and polynomial time are given Furthermore, probabfllsUc parallelism algorithms requiring simultaneously loganthmic time and a polynomml number of processors are also given. © 1984, ACM. All rights reserved.
Duke Scholars
Published In
Journal of the ACM (JACM)
DOI
EISSN
1557-735X
ISSN
0004-5411
Publication Date
March 30, 1984
Volume
31
Issue
2
Start / End Page
401 / 421
Related Subject Headings
- Computation Theory & Mathematics
- 08 Information and Computing Sciences
Citation
APA
Chicago
ICMJE
MLA
NLM
Reif, J. H. (1984). Symmetric Complementation. Journal of the ACM (JACM), 31(2), 401–421. https://doi.org/10.1145/62.322436
Reif, J. H. “Symmetric Complementation.” Journal of the ACM (JACM) 31, no. 2 (March 30, 1984): 401–21. https://doi.org/10.1145/62.322436.
Reif JH. Symmetric Complementation. Journal of the ACM (JACM). 1984 Mar 30;31(2):401–21.
Reif, J. H. “Symmetric Complementation.” Journal of the ACM (JACM), vol. 31, no. 2, Mar. 1984, pp. 401–21. Scopus, doi:10.1145/62.322436.
Reif JH. Symmetric Complementation. Journal of the ACM (JACM). 1984 Mar 30;31(2):401–421.
Published In
Journal of the ACM (JACM)
DOI
EISSN
1557-735X
ISSN
0004-5411
Publication Date
March 30, 1984
Volume
31
Issue
2
Start / End Page
401 / 421
Related Subject Headings
- Computation Theory & Mathematics
- 08 Information and Computing Sciences