An Efficient Parallel Algorithm for the General Planar Monotone Circuit Value Problem
From MaRDI portal
Publication:4877521
DOI10.1137/S0097539793260775zbMath0844.68051MaRDI QIDQ4877521
Honghua Yang, Vijaya Ramachandran
Publication date: 18 August 1996
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Parallel algorithms in computer science (68W10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Distributed algorithms (68W15)
Related Items
Some Halting Problems for Abelian Sandpiles Are Undecidable in Dimension Three, A generalization of Spira's theorem and circuits with small segregators or separators, The Monotone Circuit Value Problem with Bounded Genus Is in NC, The complexity of the comparator circuit value problem