CNF and DNF succinct graph encodings
type: Item
instance of: scholarly article
title: CNF and DNF succinct graph encodings
zbMATH Open document ID: 1362.68229
author: Bireswar Das
author: Patrick Scharpfenecker
author: Jacobo Torán
published in: Information and Computation
publication date: 2017-03-16T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q19
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 6695653
zbMATH Keywords: complexity
zbMATH Keywords: succinct encoding
zbMATH Keywords: graph isomorphism
zbMATH Keywords: CNF
zbMATH Keywords: DNF
describes a project that uses: Datalog
MaRDI profile type: Publication
full work available at URL: j.ic.2016.06.009
OpenAlex ID: W2419633893
cites work: The Minimum Oracle Circuit Size Problem.
cites work: An infinite family of self-diclique digraphs
cites work: FSTTCS 2007: Foundations of software technology and theoretical computer science. 27th international conference, New Delhi, India, December 12--14, 2007. Proceedings
cites work: PP is closed under truth-table reductions
cites work: Functions computable in polynomial space
cites work: Succinct representations of graphs
cites work: Symmetric space-bounded computation
cites work: A note on succinct representations of graphs
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: Reductions to graph isomorphism
cites work: Languages represented by Boolean formulas
cites work: Q4258578
cites work: The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
DOI: 10.1016/J.IC.2016.06.009
description: scientific article; zbMATH DE number 6695653