Bounded-depth succinct encodings and the structure they imply on graphs
From MaRDI portal
Publication:722204
DOI10.1007/s00224-017-9787-4zbMath1397.68109OpenAlexW2624065397MaRDI QIDQ722204
Publication date: 23 July 2018
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-017-9787-4
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Languages represented by Boolean formulas
- Approximation hardness of dominating set problems in bounded degree graphs
- On covering graphs by complete bipartite subgraphs
- Covering graphs by the minimum number of equivalence relations
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- Some simplified NP-complete graph problems
- A hierarchy for nondeterministic time complexity
- Which problems have strongly exponential complexity?
- Graphs of small dimensions
- Succinct representations of graphs
- On Graph Complexity
- On set intersection representations of graphs
- Separating Nondeterministic Time Complexity Classes
- On completeness for NP via projection translations
- Bipartite Coverings of Graphs
- On the complexity of \(k\)-SAT
This page was built for publication: Bounded-depth succinct encodings and the structure they imply on graphs
