Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Descriptive complexity and finite models (68Q19)
Recommendations
Cites work
- scientific article; zbMATH DE number 1335887 (Why is no real title available?)
- A note on succinct representations of graphs
- An infinite family of self-diclique digraphs
- FSTTCS 2007: Foundations of software technology and theoretical computer science. 27th international conference, New Delhi, India, December 12--14, 2007. Proceedings
- Functions computable in polynomial space
- Languages represented by Boolean formulas
- PP is closed under truth-table reductions
- Reductions to graph isomorphism
- Relationships between nondeterministic and deterministic tape complexities
- Succinct representations of graphs
- Symmetric space-bounded computation
- The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
- The Minimum Oracle Circuit Size Problem.
Cited in
(3)
This page was built for publication: CNF and DNF succinct graph encodings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q515682)
