CNF and DNF succinct graph encodings
DOI10.1016/J.IC.2016.06.009zbMATH Open1362.68229OpenAlexW2419633893MaRDI QIDQ515682FDOQ515682
Patrick Scharpfenecker, Jacobo Torán, Bireswar Das
Publication date: 16 March 2017
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2016.06.009
Recommendations
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)
Cites Work
- Relationships between nondeterministic and deterministic tape complexities
- Languages represented by Boolean formulas
- Succinct representations of graphs
- A note on succinct representations of graphs
- The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
- Symmetric space-bounded computation
- Title not available (Why is that?)
- PP is closed under truth-table reductions
- Functions computable in polynomial space
- FSTTCS 2007: Foundations of software technology and theoretical computer science. 27th international conference, New Delhi, India, December 12--14, 2007. Proceedings
- The Minimum Oracle Circuit Size Problem.
- An infinite family of self-diclique digraphs
- Reductions to graph isomorphism
Cited In (2)
Uses Software
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)
