Bounded-depth succinct encodings and the structure they imply on graphs
type: Item
instance of: scholarly article
title: Bounded-depth succinct encodings and the structure they imply on graphs
zbMATH Open document ID: 1397.68109
author: Patrick Scharpfenecker
published in: Theory of Computing Systems
publication date: 2018-07-23T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6909384
zbMATH Keywords: complexity
zbMATH Keywords: succinct
zbMATH Keywords: circuits
zbMATH Keywords: biclique
zbMATH Keywords: graphs
zbMATH Keywords: NP
describes a project that uses: Datalog
MaRDI profile type: Publication
full work available at URL: s00224-017-9787-4
OpenAlex ID: W2624065397
cites work: Covering graphs by the minimum number of equivalence relations
cites work: Approximation hardness of dominating set problems in bounded degree graphs
cites work: A hierarchy for nondeterministic time complexity
cites work: On covering graphs by complete bipartite subgraphs
cites work: On Graph Complexity
cites work: Graphs of small dimensions
cites work: Q4255575
cites work: Succinct representations of graphs
cites work: Some simplified NP-complete graph problems
cites work: On the complexity of \(k\)-SAT
cites work: Which problems have strongly exponential complexity?
cites work: On set intersection representations of graphs
cites work: Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
cites work: Bipartite Coverings of Graphs
cites work: Separating Nondeterministic Time Complexity Classes
cites work: On completeness for NP via projection translations
cites work: Languages represented by Boolean formulas
cites work: Q4258578
DOI: 10.1007/S00224-017-9787-4
description: scientific article; zbMATH DE number 6909384