Bounded-depth succinct encodings and the structure they imply on graphs (Q722204): Difference between revisions

@@ Property / describes a project that uses @@
+Datalog
@@ Property / describes a project that uses: Datalog / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/s00224-017-9787-4
+Normal rank
@@ Property / OpenAlex ID @@
+W2624065397
@@ Property / OpenAlex ID: W2624065397 / rank @@
+Normal rank
@@ Property / cites work @@
+Covering graphs by the minimum number of equivalence relations
+Normal rank
@@ Property / cites work @@
+Approximation hardness of dominating set problems in bounded degree graphs
+Normal rank
@@ Property / cites work @@
+A hierarchy for nondeterministic time complexity
@@ Property / cites work: A hierarchy for nondeterministic time complexity / rank @@
+Normal rank
@@ Property / cites work @@
+On covering graphs by complete bipartite subgraphs
+Normal rank
@@ Property / cites work @@
+On Graph Complexity
@@ Property / cites work: On Graph Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Graphs of small dimensions
@@ Property / cites work: Graphs of small dimensions / rank @@
+Normal rank
@@ Property / cites work @@
+Q4255575
@@ Property / cites work: Q4255575 / rank @@
+Normal rank
@@ Property / cites work @@
+Succinct representations of graphs
@@ Property / cites work: Succinct representations of graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Some simplified NP-complete graph problems
@@ Property / cites work: Some simplified NP-complete graph problems / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of \(k\)-SAT
@@ Property / cites work: On the complexity of \(k\)-SAT / rank @@
+Normal rank
@@ Property / cites work @@
+Which problems have strongly exponential complexity?
+Normal rank
@@ Property / cites work @@
+On set intersection representations of graphs
@@ Property / cites work: On set intersection representations of graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
+Normal rank
@@ Property / cites work @@
+Bipartite Coverings of Graphs
@@ Property / cites work: Bipartite Coverings of Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Separating Nondeterministic Time Complexity Classes
+Normal rank
@@ Property / cites work @@
+On completeness for NP via projection translations
+Normal rank
@@ Property / cites work @@
+Languages represented by Boolean formulas
@@ Property / cites work: Languages represented by Boolean formulas / rank @@
+Normal rank
@@ Property / cites work @@
+Q4258578
@@ Property / cites work: Q4258578 / rank @@
+Normal rank