Constant width planar computation characterizes ACC\(^{0}\)
From MaRDI portal
Publication:2432526
DOI10.1007/s00224-005-1258-7zbMath1103.68094OpenAlexW2085128339MaRDI QIDQ2432526
Publication date: 25 October 2006
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-005-1258-7
Graph theory (including graph drawing) in computer science (68R10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Nonuniform ACC Circuit Lower Bounds ⋮ Classification of Planar Upward Embedding ⋮ Positive and negative proofs for circuits and branching programs ⋮ Upward planar graphs and their duals