Symmetric Complementation
DOI10.1145/62.322436zbMATH Open0632.68062OpenAlexW2293273465MaRDI QIDQ3769977FDOQ3769977
Authors: J. Reif 
Publication date: 1984
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/62.322436
Recommendations
complexity classeslogarithmic spacepolynomial timegraph problemslogarithmic timepolynomial number of processorsprobabilistic parallelism algorithmsprobabilistic sequential algorithmssymmetric complementing games
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Applications of game theory (91A80)
Cited In (16)
- Absorbing random walks and the NAE2SAT problem
- Optimal parallel randomized algorithms for sparse addition and identification
- Complete problems for symmetric logspace involving free groups
- Complement, complexity, and symmetric representation
- Frameworks for designing in-place graph algorithms
- A framework for in-place graph algorithms
- Depth-first search is inherently sequential
- Sublinear-space approximation algorithms for Max \(r\)-SAT
- The complexity of planarity testing
- Approximation in (Poly-) Logarithmic Space
- Symmetric variation
- Planarity testing in parallel
- On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls
- Expected parallel time and sequential space complexity of graph and digraph problems
- Planarity testing revisited
- Approximation in (poly-) logarithmic space
This page was built for publication: Symmetric Complementation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3769977)
